Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define ll long long
- #define ld long double
- #define ull unsigned long long
- #define F first
- #define S second
- #define uint unsigned int
- #define forn(i, n) for (int i = 0; i < n; i++)
- using namespace std;
- ld g[150][150];
- int main()
- {
- cin.tie(0);
- cout.tie(0);
- ios_base::sync_with_stdio(false);
- // freopen("12.in", "r", stdin);
- // freopen("output.txt", "w", stdout);
- int n;
- cin >> n;
- vector <pair <int, int>> a;
- set <pair <int, int>> st;
- forn(i, 150)
- forn(j, 150)
- if (i != j) g[i][j] = 1e10;
- else g[i][j] = 0;
- vector <pair <ld, pair <int, int>>> sp;
- forn(i, n)
- {
- int x1, y1, x2, y2;
- ld q;
- cin >> x1 >> y1 >> x2 >> y2 >> q;
- x1 *= 2;
- x2 *= 2;
- y1 *= 2;
- y2 *= 2;
- int xt = (x1 + x2) / 2;
- int yt = (y1 + y2) / 2;
- if (st.find({xt, yt}) == st.end()) a.pb({xt, yt});
- if (st.find({x1, y1}) == st.end()) a.pb({x1, y1});
- if (st.find({x2, y2}) == st.end()) a.pb({x2, y2});
- int t, t1, t2;
- forn(j, int(a.size()))
- if (a[j] == make_pair(x1, y1)) {t1 = j; break;}
- forn(j, int(a.size()))
- if (a[j] == make_pair(x2, y2)) {t2 = j; break;}
- forn(j, int(a.size()))
- if (a[j] == make_pair(xt, yt)) {t = j; break;}
- st.insert({x1, y1});
- st.insert({x2, y2});
- st.insert({xt, yt});
- g[t1][t] = q / 2;
- g[t][t1] = q / 2;
- g[t][t2] = q / 2;
- g[t2][t] = q / 2;
- sp.pb({q / 2, {t1, t}});
- sp.pb({q / 2, {t, t2}});
- }
- forn(c, int(a.size()))
- forn(i, int(a.size()))
- forn(j, int(a.size()))
- if (g[i][j] > g[i][c] + g[c][j])
- g[i][j] = g[i][c] + g[c][j];
- ld mx = 1e9;
- int vv;
- for(int j = 0; j < int(a.size()); j++)
- {
- int v = j;
- if (a[v].F % 2 != 0 || a[v].S % 2 != 0) continue;
- ld mn = 0;
- for(int i = 0; i < int(sp.size()); i++)
- {
- ld time = sp[i].F;
- ld t1 = g[v][sp[i].S.F];
- ld t2 = g[v][sp[i].S.S];
- if (t2 > t1) swap(t1, t2);
- ld now = min(t1 - t2, time);
- time -= now;
- now += time / 2;
- now += t2;
- if (now > mn) mn = now;
- }
- if (mn < mx) {mx = mn; vv = j;}
- }
- cout << a[vv].F / 2 << ' ' << a[vv].S / 2 << '\n' << fixed << setprecision(5) << mx;
- return 0;
- }
- //LUERFDGLLH
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement