Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #pragma comment(linker, "/stack:200000000")
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <set>
- #include <map>
- #include <deque>
- #include <cmath>
- #include <queue>
- #include <random>
- #include <bitset>
- #include <time.h>
- #include <string>
- #include <chrono>
- #include <cstdio>
- #include <vector>
- #include <cstdlib>
- #include <iomanip>
- #include <cassert>
- #include <iostream>
- #include <algorithm>
- #include <unordered_map>
- #include <unordered_set>
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- #define itn int
- #define endl '\n'
- #define mp make_pair
- #define pbc push_back
- #define pob pop_back()
- #define empb emplace_back
- #define sp system("pause")
- #define queuel queue<long long>
- #define matrix vector<vector<ll>>
- #define all(x) (x).begin(),(x).end()
- #define rall(x) (x).rbegin(),(x).rend()
- #define pin(p) cin >> p.first >> p.second;
- #define rev(v) reverse(v.begin(),v.end());
- #define mx(v) max_element(v.begin(), v.end());
- #define mn(v) min_element(v.begin(), v.end());
- #define dig(c) (c >=' 0' && c <= '9') ? 1 : 0
- #define sout(s, c) for(auto i : s) cout << i << c;
- #define pout(p) cout << p.first << " " << p.second;
- #define er(v, l, r) erase(v.begin() + l, v.begin() + r);
- #define vin(v) for(ll i = 0; i < v.size(); i++) cin >> v[i];
- #define vout(v, c) for(int i = 0; i < v.size(); i++) cout << v[i] << c;
- #define pushi(v, a) for(int i = 0; i < a.size(); i++) v.push_back(a[i]);
- #define sin(s, n) for(int i = 0; i < n; i++){int a; cin >> a; s.insert(a);}
- #define fastio() ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- using namespace std;
- /*▄███████▀▀▀▀▀▀███████▄
- ░▐████▀▒ЗАПУСКАЕМ▒▀██████▄
- ░███▀▒▒▒▒▒ДЯДЮ▒▒▒▒▒▒▀█████
- ░▐██▒▒▒▒▒▒БОГДАНА▒▒▒▒▒████▌
- ░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
- ░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
- ░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
- ░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
- ░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
- ░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
- ░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
- ░░░░▄██████████████▒▒▐▌
- ░░░▀███▀▀████▀█████▀▒▌
- ░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
- ░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐*/
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- //++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++
- const ll INF = 1000LL * 1000 * 1000 * 1000 * 1000 * 1000;
- const int inf = 1000000000 + 228;
- const ld PI = acos(-1.0);
- const ll mod1 = inf * inf + 1337 * 42 + 57 * 179 + 228;
- const ll mod2 = inf + 9;
- const ll bigmod = 1LL * inf * 100 + 3;
- const int MAXN = 10005;
- const ld EPS = 1e-10;
- const int N = 300228;
- ll hp = 1e6 + 3;
- struct point
- {
- ld x, y;
- };
- struct line
- {
- ld a,b,c;
- };
- line getln(point a, point b)
- {
- line m;
- m.a = b.y - a.y;
- m.b = a.x - b.x;
- m.c = -(m.a * a.x + m.b * a.y);
- return m;
- }
- ld det(ld a, ld b, ld c, ld d)
- {
- return a * d - b * c;
- }
- point intersect(line m, line n)
- {
- ld zn = det(m.a, m.b, n.a, n.b);
- if (abs(zn) < EPS)
- {
- return { inf, inf };
- }
- point res;
- res.x = -det(m.c, m.b, n.c, n.b) / zn;
- res.y = -det(m.a, m.c, n.a, n.c) / zn;
- return res;
- }
- ld hypot(point a, point b)
- {
- return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
- }
- bool belong(point a, point b, point c)
- {
- return abs(hypot(a, b) - hypot(a, c) - hypot(b, c)) < EPS;
- }
- bool operator==(point a, point b)
- {
- return abs(a.x - b.x) < EPS && abs(a.y - b.y) < EPS;
- }
- bool kekkek(line a, line b)
- {
- return abs(det(a.a, a.b, b.a, b.b)) < EPS && abs(det(a.b, a.c, b.b, b.c)) < EPS && abs(det(a.a, a.c, b.a, b.c)) < EPS;
- }
- point operator+(point a, point b)
- {
- return { a.x + b.x, a.y + b.y };
- }
- point vec(point a, point b)
- {
- return { b.x - a.x, b.y - a.y };
- }
- point operator/(point a, ld x)
- {
- return { a.x / x, a.y / x };
- }
- ld operator*(point a, point b)
- {
- return a.x * b.y - a.y* b.x;
- }
- ld operator%(point a, point b)
- {
- return a.x * b.x + a.y * b.y;
- }
- bool help(point a, vector<point > b)
- {
- ld sum = 0;
- for (int i = 0; i < b.size(); ++i)
- {
- point x = b[i];
- point y = b[(i + 1) % b.size()];
- if (a == x || belong(x, y, a))
- {
- return 1;
- }
- sum += atan2(vec(a, x) * vec(a, y), vec(a, x) % vec(a, y));
- }
- return abs(abs(sum) - 2 * PI) < EPS ;
- }
- bool check(point a, point b, vector<point> kek)
- {
- point mid = (a + b) / 2;
- if (help(mid, kek)) return 0;
- line fs = getln(a, b);
- for (int i = 0; i < kek.size(); ++i)
- {
- point ka = kek[i];
- point now = kek[(i + 1) % kek.size()];
- line ss = getln(ka, now);
- point x = intersect(ss, fs);
- if (kekkek(fs, ss) && (belong(a,b,ka) && belong(a,b,now))) return 0;
- if (x == ka || x == now)
- {
- continue;
- }
- if (belong(ka, now, x) && belong(a,b,x))
- {
- return 0;
- }
- }
- return 1;
- }
- signed main()
- {
- fastio();
- int n;
- cin >> n;
- vector<point> a(n);
- for (int i = 0; i < n; ++i)
- {
- cin >> a[i].x >> a[i].y;
- }
- int m;
- cin >> m;
- vector<point> x(m);
- for (int i = 0; i < m; ++i)
- {
- cin >> x[i].x >> x[i].y;
- }
- vector<vector<ld>> d(n + m, vector<ld>(n + m, inf));
- for (int i = 0; i < n + m; ++i) d[i][i] = 0;
- for (int i = m; i < n + m - 1; ++i)
- {
- d[i][i + 1] = d[i + 1][i] = hypot(a[i - m], a[i - m + 1]);
- }
- d[n + m - 1][m] = d[m][n + m - 1] = hypot(a[n - 1], a[0]);
- for (int i = 0; i < m; ++i)
- {
- for (int j = m; j < n + m; ++j)
- {
- if (check(x[i], a[j - m], a))
- {
- d[i][j] = d[j][i] = hypot(x[i], a[j - m]);
- }
- }
- }
- for (int i = m; i < n + m; ++i)
- {
- for (int j = m; j < n + m; ++j)
- {
- if (i == m && j == m + 2 )
- {
- cout << "";
- }
- if (i == m + 2 && j == m)
- {
- cout << "";
- }
- if (check(a[i - m], a[j - m], a))
- {
- d[i][j] = d[j][i] = hypot(a[i - m], a[j - m]);
- }
- }
- }
- for (int i = 0; i < m; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- if (check(x[i], x[j], a))
- {
- d[i][j] = d[j][i] = hypot(x[i], x[j]);
- }
- }
- }
- /*
- for (int i = 0; i < n + m; ++i)
- {
- for (int j = 0; j < n + m; ++j)
- {
- cout << d[i][j] << ' ';
- }
- cout << endl;
- }
- sp;*/
- for (int k = 0; k < n + m;++k)
- {
- for (int i = 0; i < n + m; ++i)
- {
- for (int j = 0; j < n + m; ++j)
- {
- if (i == 0 && j == 5)
- {
- cout << "";
- }
- if (d[i][k] + d[k][j] - EPS < d[i][j])
- {
- d[i][j] = d[i][k] + d[k][j];
- }
- }
- }
- }
- ld ans = 0;
- //cout << endl;
- /*for (int i = 0; i < n + m; ++i)
- {
- for (int j = 0; j < n + m; ++j)
- {
- cout << d[i][j] << ' ';
- }
- cout << endl;
- }
- sp;
- for (int i = 0; i < m; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- cout << d[i][j] << ' ';
- }
- cout << endl;
- }
- sp;*/
- for (int i = 0; i < m; ++i)
- {
- for (int j = 0; j < m; ++j)
- {
- if (d[i][j] + EPS > ans)
- {
- ans = d[i][j];
- }
- }
- }
- cout << fixed << setprecision(20) << ans;
- //sp;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement