#include using namespace std; const double INF = 1e9; const double EPS = 1e-9; bool eq(double a, double b) { return fabs(a - b) < EPS; } bool lt(double a, double b) { return a < b && !eq(a, b); } struct pt { double x, y; pt() {} pt(double _x, double _y) : x(_x), y(_y) {} pt operator- (const pt &p) const { return pt(x - p.x, y - p.y); } pt operator+ (const pt &p) const { return pt(x + p.x, y + p.y); } pt operator* (double d) const { return pt(x * d, y * d); } pt operator/ (double d) const { return (*this) * (1 / d); } pt rotate90() const { return pt(-y, x); } pt norm() const { return (*this) / d(); } double operator* (const pt &p) const { return x * p.y - y * p.x; } double operator% (const pt &p) const { return x * p.x + y * p.y; } double d2() const { return (*this) % (*this); } double d() const { return sqrt(d2()); } bool operator< (const pt &p) const { return lt(y, p.y) || eq(y, p.y) && lt(x, p.x); } bool operator==(const pt &p) const { return eq(x, p.x) && eq(y, p.y); } }; pt mirror(pt a, pt b, pt p) { pt v = (b - a).norm(); pt n = v.rotate90(); pt res = p + n * (-2 * ((p - a) % n)); return res; } double dist(pt a, pt b, pt p) { return (p - (p + mirror(a, b, p))*0.5).d(); } bool intersect(double x1, double x2, double x3, double x4) { double l1 = min(x1, x2), r1 = max(x1, x2); double l2 = min(x3, x4), r2 = max(x3, x4); return !lt(min(r1, r2), max(l1, l2)); } int sign(double x) { if (lt(0, x)) return 1; if (lt(x, 0)) return -1; return 0; } bool intersect(pt A, pt B, pt C, pt D) { bool res = 1; res &= intersect(A.x, B.x, C.x, D.x); res &= intersect(A.y, B.y, C.y, D.y); res &= sign((C - A) * (B - A)) * sign((D - A) * (B - A)) <= 0; res &= sign((A - C) * (D - C)) * sign((B - C) * (D - C)) <= 0; return res; } struct polygon { int n; vector a; void read() { scanf("%d", &n); a.resize(n); for (int i = 0; i < n; i++) { int x, y; scanf("%d%d", &x, &y); a[i] = pt(x, y); } double sumang = 0; for (int i = 0; i < n; i++) { pt u = a[i], v = a[(i + 1) % n]; double ang = atan2(u * v, u % v); sumang += ang; } if (sumang < 0) { reverse(a.begin(), a.end()); } } }; optional intersect2(pt a, pt c, pt d) { if (!intersect(pt(0, 0), a * INF, c, d)) { return nullopt; } if (eq((c - a) * (d - a), 0)) { return nullopt; } // (c - bt) * (d - bt) == 0 // (c.x - b.x*t) * (d.y - b.y*t) - (c.y - b.y*t) * (d.x - b.x*t) == 0 // t * (-b.x*d.y + -b.y*c.x + b.y*d.x + b.x*c.y) = -c.x*d.y +d.x*c.y double nom = (-c.x * d.y + d.x * c.y); double denom = (-a.x * d.y - a.y * c.x + a.y * d.x + a.x*c.y); assert(!eq(denom, 0)); double t = nom / denom; pt u = a * t; pt mx = max(c, d); if (u == mx) return nullopt; return t; } struct event { double x; int type; int id; bool operator< (const event &e) const { if (eq(x, e.x)) { return type < e.type; } return x < e.x; } }; vector check(pt a, pt c, pt d, bool inv, int id) { vector res; if (eq(a * c, 0) && (a % c) > 0) { double t = c.d() / a.d(); if (inv) t = 1 / t; res.push_back(event{t, -10, id}); res.push_back(event{t, +10, id}); } if (eq((c - a) * (d - a), 0)) { if (lt(0, a % c)) { double t1 = c.d() / a.d(); double t2 = d.d() / a.d(); if (inv) { t1 = 1 / t1; t2 = 1 / t2; } if (t1 > t2) swap(t1, t2); res.push_back(event{t1, -10, id}); res.push_back(event{t2, +10, id}); return res; } else { return res; } } auto ot = intersect2(a, c, d); if (!ot.has_value()) { return res; } double t = ot.value(); if (inv) t = 1.0 / t; event e; e.x = t; e.type = sign(c * d); e.id = id; res.push_back(e); return res; } int main() { polygon a, b; a.read(); b.read(); vector vct; for (int i = 0; i < a.n; i++) { for (int j = 0; j < b.n; j++) { for (auto e : check(a.a[i], b.a[j], b.a[(j + 1) % b.n], false, i)) { vct.push_back(e); } for (auto e : check((a.a[i]+a.a[(i+1)%a.n])*0.5, b.a[j], b.a[(j + 1) % b.n], false, a.n+i)) { vct.push_back(e); } for (auto e : check(b.a[j], a.a[i], a.a[(i + 1) % a.n], true, a.n*2 + j)) { vct.push_back(e); } for (auto e : check((b.a[j]+b.a[(j+1)%b.n])*0.5, a.a[i], a.a[(i + 1) % a.n], true, a.n*2+b.n + j)) { vct.push_back(e); } } } sort(vct.begin(), vct.end()); double ans = 0; vector csum(a.n * 2 + b.n * 2); int ok = csum.size(); for (auto ev : vct) { // cout << ev.x << " " << ev.type << " " << ev.id << " " << ok << ";"; // for (int i = 0; i < (int)csum.size(); i++) cout << " " << csum[i]; // cout << endl; if (ok == csum.size()) { ans = max(ans, ev.x); } ok -= csum[ev.id] <= 0; csum[ev.id] += ev.type; ok += csum[ev.id] <= 0; } printf("%.15f\n", ans); }