Advertisement
Guest User

Untitled

a guest
Sep 10th, 2019
280
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define F first
  8. #define S second
  9. #define uint unsigned int
  10. #define forn(i, n) for (int i = 0; i < n; i++)
  11.  
  12. using namespace std;
  13.  
  14. ld g[150][150];
  15. int main()
  16. {
  17.  
  18. cin.tie(0);
  19. cout.tie(0);
  20. ios_base::sync_with_stdio(false);
  21. // freopen("12.in", "r", stdin);
  22. // freopen("output.txt", "w", stdout);
  23. int n;
  24. cin >> n;
  25. vector <pair <int, int>> a;
  26. set <pair <int, int>> st;
  27. forn(i, 150)
  28. forn(j, 150)
  29. if (i != j) g[i][j] = 1e10;
  30. else g[i][j] = 0;
  31. vector <pair <ld, pair <int, int>>> sp;
  32. forn(i, n)
  33. {
  34. int x1, y1, x2, y2;
  35. ld q;
  36. cin >> x1 >> y1 >> x2 >> y2 >> q;
  37. x1 *= 2;
  38. x2 *= 2;
  39. y1 *= 2;
  40. y2 *= 2;
  41. int xt = (x1 + x2) / 2;
  42. int yt = (y1 + y2) / 2;
  43. if (st.find({xt, yt}) == st.end()) a.pb({xt, yt});
  44. if (st.find({x1, y1}) == st.end()) a.pb({x1, y1});
  45. if (st.find({x2, y2}) == st.end()) a.pb({x2, y2});
  46. int t, t1, t2;
  47. forn(j, int(a.size()))
  48. if (a[j] == make_pair(x1, y1)) {t1 = j; break;}
  49. forn(j, int(a.size()))
  50. if (a[j] == make_pair(x2, y2)) {t2 = j; break;}
  51. forn(j, int(a.size()))
  52. if (a[j] == make_pair(xt, yt)) {t = j; break;}
  53. st.insert({x1, y1});
  54. st.insert({x2, y2});
  55. st.insert({xt, yt});
  56. g[t1][t] = q / 2;
  57. g[t][t1] = q / 2;
  58. g[t][t2] = q / 2;
  59. g[t2][t] = q / 2;
  60. sp.pb({q / 2, {t1, t}});
  61. sp.pb({q / 2, {t, t2}});
  62. }
  63.  
  64. forn(c, int(a.size()))
  65. forn(i, int(a.size()))
  66. forn(j, int(a.size()))
  67. if (g[i][j] > g[i][c] + g[c][j])
  68. g[i][j] = g[i][c] + g[c][j];
  69. ld mx = 1e9;
  70. int vv;
  71. for(int j = 0; j < int(a.size()); j++)
  72. {
  73. int v = j;
  74. if (a[v].F % 2 != 0 || a[v].S % 2 != 0) continue;
  75. ld mn = 0;
  76. for(int i = 0; i < int(sp.size()); i++)
  77. {
  78. ld time = sp[i].F;
  79. ld t1 = g[v][sp[i].S.F];
  80. ld t2 = g[v][sp[i].S.S];
  81. if (t2 > t1) swap(t1, t2);
  82. ld now = min(t1 - t2, time);
  83. time -= now;
  84. now += time / 2;
  85. now += t2;
  86. if (now > mn) mn = now;
  87. }
  88. if (mn < mx) {mx = mn; vv = j;}
  89.  
  90. }
  91. cout << a[vv].F / 2 << ' ' << a[vv].S / 2 << '\n' << fixed << setprecision(5) << mx;
  92. return 0;
  93. }
  94. //LUERFDGLLH
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement