#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int MaxN = 2e5 + 10; const int INF = 1e9; const double EPS = 1e-5; struct Point { double x, y; Point() { } Point(double _x, double _y) : x(_x), y(_y) { } double len(const Point &other) const { return hypot(x - other.x, y - other.y); } bool operator< (const Point &other) const { if (x != other.x) { return x < other.x; } return y < other.y; } void read() { scanf("%lf%lf", &x, &y); } }; struct Circle { double x, y, r; Point center; void read() { scanf("%lf%lf%lf", &x, &y, &r); center = Point(x, y); } bool inside(const Circle &other) const { return center.len(other.center) + other.r <= r + EPS; } }; bool cmp(const pair < pair < double, double >, pair < int, int > > &a, const pair < pair < double, double >, pair < int, int > > &b) { return (a.first.first + a.first.second) / 2.0 + a.second.first * EPS > (b.first.first + b.first.second) / 2.0 + b.second.first * EPS; } double solve() { int n; scanf("%d", &n); vector < Circle > circles(n), c; set < pair < pair < double, double >, double > > st; for (int i = 0; i < n; ++i) { circles[i].read(); if (st.count(make_pair(make_pair(circles[i].x, circles[i].y), circles[i].r))) { n--; i--; continue; } st.insert(make_pair(make_pair(circles[i].x, circles[i].y), circles[i].r)); } int m; scanf("%d", &m); vector < Point > polygon(m); for (int i = 0; i < m; ++i) { polygon[i].read(); } for (int i = 0; i < n; ++i) { bool ok = true; for (int j = 0; j < n; ++j) { if (j != i && circles[j].inside(circles[i])) { ok = false; } } if (ok == true) { c.push_back(circles[i]); } } n = (int)c.size(); vector < Point > ins; for (int i = 0; i < n; ++i) { ins.push_back(Point(c[i].x - c[i].r, c[i].y)); ins.push_back(Point(c[i].x + c[i].r, c[i].y)); ins.push_back(Point(c[i].x, c[i].y - c[i].r)); ins.push_back(Point(c[i].x, c[i].y + c[i].r)); for (int j = i + 1; j < n; ++j) { if (c[i].center.len(c[j].center) >= c[i].r + c[j].r) { continue; } double len = c[i].center.len(c[j].center); //R1^2-d^2 = R2^2-(L-d)^2 //R1^2=R2^2-L^2+2*L*d //d = (R1^2-r2^2+L^2)/2*L double d = (c[i].r * c[i].r - c[j].r * c[j].r + len * len) / (2 * len); double h = sqrtl(c[i].r * c[i].r - d * d); double a = c[i].y - c[j].y; double b = c[j].x - c[i].x; double ab = sqrt(a * a + b * b); double fx = c[i].x + (c[j].x - c[i].x) * d / len; double fy = c[i].y + (c[j].y - c[i].y) * d / len; ins.push_back(Point(fx + a / ab * h, fy + b / ab * h)); ins.push_back(Point(fx - a / ab * h, fy - b / ab * h)); } } for (int i = 0; i < m; ++i) { ins.push_back(polygon[i]); Point u = polygon[i]; Point v = polygon[(i + 1) % m]; double La = v.y - u.y; double Lb = u.x - v.x; double Lc = u.y * v.x - u.x * v.y; double Ld = sqrt(La * La + Lb * Lb); La /= Ld; Lb /= Ld; Lc /= Ld; for (int j = 0; j < n; ++j) { double L = abs(La * c[j].x + Lb * c[j].y + Lc); if (L >= c[j].r) { continue; } double Ma = -Lb; double Mb = La; double Mc = -Ma * c[j].x - Mb * c[j].y; // La * x + Lb * y + Lc = 0 // Ma * x + Mb * y + Mc = 0 double det = La * Mb - Lb * Ma; double detX = -Lc * Mb + Lb * Mc; double detY = -La * Mc + Lc * Ma; Point intr = Point(detX / det, detY / det); assert (abs(Ma * intr.x + Mb * intr.y + Mc) < EPS); assert (abs(La * intr.x + Lb * intr.y + Lc) < EPS); double dist = sqrt(c[j].r * c[j].r - L * L); ins.push_back(Point(intr.x + Lb * dist, intr.y - La * dist)); assert (abs(hypot(c[j].x - ins.back().x, c[j].y - ins.back().y) - c[j].r) < EPS); ins.push_back(Point(intr.x - Lb * dist, intr.y + La * dist)); assert (abs(hypot(c[j].x - ins.back().x, c[j].y - ins.back().y) - c[j].r) < EPS); } } double ans = 0.0; sort(ins.begin(), ins.end()); for (int i = 0, j, k; i < (int)ins.size(); i = j) { for (j = i; j < (int)ins.size() && abs(ins[i].x - ins[j].x) == 0; ++j); if (j == (int)ins.size()) { continue; } for (k = j; k < (int)ins.size() && abs(ins[k].x - ins[j].x) == 0; ++k); double xl = ins[i].x, xr = ins[j].x; vector < pair < pair < double, double >, pair < int, int > > > all; for (int it = 0; it < n; ++it) { if (xl >= c[it].x - c[it].r && xr <= c[it].x + c[it].r) { //(xl - c[it].x)^2 + (yl - c[it].y)^2 = r^2 double yl1 = c[it].y + sqrtl(c[it].r * c[it].r - (xl - c[it].x) * (xl - c[it].x)); double yl2 = c[it].y - sqrtl(c[it].r * c[it].r - (xl - c[it].x) * (xl - c[it].x)); double yr1 = c[it].y + sqrtl(c[it].r * c[it].r - (xr - c[it].x) * (xr - c[it].x)); double yr2 = c[it].y - sqrtl(c[it].r * c[it].r - (xr - c[it].x) * (xr - c[it].x)); all.push_back(make_pair(make_pair(yl1, yr1), make_pair(+1, it))); all.push_back(make_pair(make_pair(yl2, yr2), make_pair(-1, it))); } } for (int it = 0; it < m; ++it) { Point a = polygon[it], b = polygon[(it + 1) % m]; if (a.x > b.x) { swap(a.x, b.x); swap(a.y, b.y); } if (a.x <= xl && xr <= b.x) { double yl = (xl - a.x) / (b.x - a.x) * (b.y - a.y) + a.y; double yr = (xr - a.x) / (b.x - a.x) * (b.y - a.y) + a.y; all.push_back(make_pair(make_pair(yl, yr), make_pair(0, it))); } } sort(all.begin(), all.end(), cmp); pair < double, double > last; for (int i = 0, bal = 0, polyBal = 0; i < (int)all.size(); ++i) { if (all[i].second.first != 0) { int id = all[i].second.second; bool need = false; if (bal == 0 && polyBal == 1) { last = all[i].first; need = true; } bal += all[i].second.first; if (bal == 0 && polyBal == 1) { ans += (xr - xl) * (abs(all[i].first.first - last.first) + abs(all[i].first.second - last.second)) / 2.0; need = true; } if (need && polyBal == 1) { Point A = Point(xl, all[i].first.first); Point B = Point(xr, all[i].first.second); double ang = acosl((c[id].r * c[id].r + c[id].r * c[id].r - ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y))) / (2 * c[id].r * c[id].r)); ans += 0.5 * c[id].r * c[id].r * (ang - sin(ang)); } } else { if (polyBal == 1) { if (bal != 0) { ans += (xr - xl) * (abs(all[i].first.first - last.first) + abs(all[i].first.second - last.second)) / 2.0; } polyBal = 0; } else { polyBal = 1; last = all[i].first; } } } } return ans; } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int t = 1; // scanf("%d", &t); while (t --> 0) { printf("%.12lf\n", solve()); } return 0; }