<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

435. UFO Circles
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Recently, British scientists have discovered a huge field of grain on the Mars. They claim that this field is strictly two-dimensional (flat) and spans a nearly infinite area. There are some strange circles on this field, supposedly left by the UFOs. The UFOs are also very strange. When an UFO lands on a grain, the grain in the landing area is burned to ashes. But when an UFO lands on field which is already burned, the inverse grain grows instantly in that place. When an UFO lands on inverse grain field, it is burned just like normal grain. There were cases of UFO landings on areas with both grain fields and burned fields. In these cases the parts with grain were burned, and inverse grain was grown on the other parts.

You are hired by the scientists to help them with calculations. They require you to calculate total area of burned fields and total area of fields with inverse grain.

Input
The first line of input will contain the number of circles N (1 ≤ N ≤ 100). Each of the following N lines contains three integer numbers x, y and r, where  are the coordinates of circle center and r is the circle radius. All numbers do not exceed 1000 by absolute value. All circles are different, and all radii are positive.

Output
Output should contain two numbers delimited by a space — the areas you should calculate. These numbers should be accurate to at least three digits after the decimal point. The first number should be the total area of burned fields, the second one should be the total area of inverse grain.

Example(s)
sample input
sample output
2
0 0 5
0 3 1
75.39822 3.14159

<|response|>
## 1) Abridged problem statement

You are given **N (1 ≤ N ≤ 100)** circles (center \((x,y)\), radius \(r>0\)) on an infinite 2D plane.

Initially the whole plane is **normal grain**. For each circle, a UFO “lands” on the disk and **toggles** the state inside that disk:

- grain → burned  
- burned → inverse grain  
- inverse grain → burned  

After all landings, for any point \(p\), let \(c(p)\) = number of disks covering \(p\). Then:
- \(c(p)=0\): normal grain (ignore)
- \(c(p)\) odd: **burned**
- \(c(p)\) even and \(>0\): **inverse grain**

Output two numbers:
1) total burned area, 2) total inverse-grain area, with ≥ 3 decimal digits accuracy.

---

## 2) Key observations needed to solve the problem

1. **Only parity matters**  
   The final state depends only on whether the coverage count is odd or even.

2. **Coverage changes only at circle boundaries**  
   Within each region bounded by circle arcs, \(c(p)\) is constant. So the plane is partitioned into faces of a circle arrangement.

3. **Compute face areas without explicitly building faces**  
   Using **Green’s theorem**, area can be computed as a line integral over the boundary:
   \[
   A = \frac{1}{2}\oint (x\,dy - y\,dx)
   \]
   For a circular arc, this integral has a closed form.

4. **Process boundary arcs circle-by-circle**  
   On each circle, intersection points split the circumference into arcs. Each arc separates two adjacent faces: one “just inside” the circle and one “just outside”.

5. **Classify each side by sampling**  
   Take a point slightly inside and slightly outside the arc and count how many circles contain it (strictly). This tells whether that adjacent face is burned (odd) or inverse (even>0) or ignored (0).

---

## 3) Full solution approach

### Step A: Build arc “events” on each circle
For each circle \(i\):
- Collect all intersection points between circle \(i\) and every other circle \(j\).
- Add **two guaranteed points** on circle \(i\) (e.g., leftmost and rightmost points) so we always have at least 2 events even if there are no intersections.
- For every event point \(p\), compute its polar angle around center \(c_i\): \(\theta = \text{atan2}(p_y-c_{iy}, p_x-c_{ix})\).
- Sort events by angle and remove duplicates by angle (tangencies can create repeated points).

Adjacent events in this sorted list define an arc segment on that circle. Include wrap-around (last to first).

### Step B: For each arc, determine coverage parity on both sides
For each arc from event \(j\) to \(j+1\):
- Let angles be \(\theta_1,\theta_2\) (wrap \(\theta_2\) by adding \(2\pi\) if needed so \(\theta_2 \ge \theta_1\)).
- Mid-angle \(\theta_m = (\theta_1+\theta_2)/2\), direction \(u=(\cos\theta_m,\sin\theta_m)\).
- Test points:
  - inside: \(p_{\text{in}} = c_i + u \cdot (r_i - \varepsilon)\)
  - outside: \(p_{\text{out}} = c_i + u \cdot (r_i + \varepsilon)\)
- Count circles strictly containing each test point:
  \[
  cnt(p) = |\{k : \|p-c_k\| < r_k - \text{EPS}\}|
  \]
This gives the face type on each side.

### Step C: Add signed area contributions using Green’s theorem
For an arc on circle centered at \((c_x,c_y)\) radius \(r\) from angle \(\theta_1\) to \(\theta_2\) (CCW, with \(\theta_2\ge\theta_1\)), the signed contribution is:

\[
\text{piece}=
\frac{1}{2}\left(
r c_x(\sin\theta_2-\sin\theta_1)
- r c_y(\cos\theta_2-\cos\theta_1)
+ r^2(\theta_2-\theta_1)
\right)
\]

Now:
- If the **inside** face is burned (odd) → add `piece` to burned total.
- If the **inside** face is inverse (even>0) → add `piece` to inverse total.
- For the **outside** face, the same arc is traversed with opposite orientation in that face’s boundary, so we **subtract** `piece` for that face classification (and ignore if cnt=0 to avoid including the infinite outside region).

Summing over all arcs of all circles yields the correct total areas (internal boundaries cancel; each finite face contributes exactly once with correct sign).

### Complexity
- Circle intersections: \(O(N^2)\)
- Total arcs: \(O(N^2)\)
- For each arc we count coverage by scanning all circles: \(O(N)\)

Total: **\(O(N^3)\)** with \(N \le 100\) ⇒ about \(10^6\) circle containment checks, fine.

---

## 4) C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

using coord_t = double;

static const coord_t EPS = 1e-9;
static const coord_t PI  = acos(-1.0);

struct Point {
    coord_t x, y;
    Point(coord_t x=0, coord_t y=0) : x(x), y(y) {}

    Point operator+(const Point& o) const { return Point(x + o.x, y + o.y); }
    Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }
    Point operator*(coord_t k) const { return Point(x * k, y * k); }

    coord_t norm() const { return hypot(x, y); }
    coord_t angle() const { return atan2(y, x); }

    Point perp() const { return Point(-y, x); }

    Point unit() const {
        coord_t n = norm();
        return Point(x / n, y / n);
    }
};

// Signed area contribution for CCW arc from p1 to p2 on circle (center, r).
// Uses closed-form of 1/2 ∫ (x dy - y dx) along the arc.
static coord_t arc_area(const Point& center, coord_t r, const Point& p1, const Point& p2) {
    coord_t t1 = (p1 - center).angle();
    coord_t t2 = (p2 - center).angle();
    if (t2 < t1 - EPS) t2 += 2 * PI; // unwrap so t2 >= t1

    coord_t cx = center.x, cy = center.y;
    coord_t area = r * cx * (sin(t2) - sin(t1))
                 - r * cy * (cos(t2) - cos(t1))
                 + r * r  * (t2 - t1);
    return area / 2.0;
}

// Circle-circle intersection: returns 0/1/2 intersection points.
// If circles are separate, contained, or same center -> returns empty.
static vector<Point> intersect_circles(const Point& c1, coord_t r1,
                                       const Point& c2, coord_t r2) {
    Point d = c2 - c1;
    coord_t dist = d.norm();

    // No intersection cases (or coincident centers)
    if (dist > r1 + r2 + EPS) return {};
    if (dist < fabs(r1 - r2) - EPS) return {};
    if (dist < EPS) return {};

    // a = distance from c1 to chord midpoint along direction to c2
    coord_t a = (r1*r1 - r2*r2 + dist*dist) / (2.0 * dist);
    coord_t h2 = r1*r1 - a*a;
    if (h2 < -EPS) return {};
    if (h2 < 0) h2 = 0; // clamp tiny negative due to precision

    coord_t h = sqrt(h2);

    Point mid = c1 + d.unit() * a;      // chord midpoint
    Point perp_dir = d.perp().unit();   // perpendicular direction

    if (h < EPS) return {mid};          // tangent
    return { mid + perp_dir * h, mid - perp_dir * h };
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Point> centers(n);
    vector<coord_t> radii(n);
    for (int i = 0; i < n; i++) {
        cin >> centers[i].x >> centers[i].y >> radii[i];
    }

    // events[i] = list of (angle, point) on circle i where arcs will be split
    vector<vector<pair<coord_t, Point>>> events(n);

    for (int i = 0; i < n; i++) {
        // Add two guaranteed points so we always have arcs even without intersections
        Point right = centers[i] + Point(radii[i], 0);
        Point left  = centers[i] - Point(radii[i], 0);
        events[i].push_back({(right - centers[i]).angle(), right});
        events[i].push_back({(left  - centers[i]).angle(), left});

        // Add intersection points with all other circles
        for (int j = 0; j < n; j++) if (i != j) {
            auto pts = intersect_circles(centers[i], radii[i], centers[j], radii[j]);
            for (auto &p : pts) {
                events[i].push_back({(p - centers[i]).angle(), p});
            }
        }

        // Sort by angle to get consecutive arcs
        sort(events[i].begin(), events[i].end(),
             [](auto &a, auto &b){ return a.first < b.first; });

        // Deduplicate by angle (tangent intersections can generate duplicates)
        vector<pair<coord_t, Point>> uniq;
        for (auto &e : events[i]) {
            if (uniq.empty() || fabs(uniq.back().first - e.first) > EPS)
                uniq.push_back(e);
        }
        events[i].swap(uniq);
    }

    // Helper: count how many circles strictly contain point p
    auto count_circles = [&](const Point& p) {
        int cnt = 0;
        for (int k = 0; k < n; k++) {
            if ((p - centers[k]).norm() < radii[k] - EPS) cnt++;
        }
        return cnt;
    };

    coord_t burned = 0.0;   // odd coverage area
    coord_t inverse = 0.0;  // even positive coverage area

    for (int i = 0; i < n; i++) {
        int m = (int)events[i].size();
        if (m < 2) continue;

        for (int j = 0; j < m; j++) {
            // Arc endpoints (wrap around)
            coord_t ang1 = events[i][j].first;
            coord_t ang2 = events[i][(j + 1) % m].first;
            Point p1 = events[i][j].second;
            Point p2 = events[i][(j + 1) % m].second;

            // unwrap ang2 so it is >= ang1
            if (ang2 < ang1) ang2 += 2 * PI;

            // Mid-angle direction used to pick points just inside/outside the arc
            coord_t mid_ang = (ang1 + ang2) / 2.0;
            Point dir(cos(mid_ang), sin(mid_ang));

            // Slight epsilon shift to avoid boundary ambiguity
            Point test_inside  = centers[i] + dir * (radii[i] - 1e-6);
            Point test_outside = centers[i] + dir * (radii[i] + 1e-6);

            int cnt_in  = count_circles(test_inside);
            int cnt_out = count_circles(test_outside);

            // Signed arc area contribution (CCW from p1 to p2)
            coord_t piece = arc_area(centers[i], radii[i], p1, p2);

            // Add contribution for inside face
            if (cnt_in % 2 == 1) burned += piece;
            else if (cnt_in > 0) inverse += piece;

            // Subtract contribution for outside face (opposite orientation there)
            if (cnt_out % 2 == 1) burned -= piece;
            else if (cnt_out > 0) inverse -= piece;
        }
    }

    cout << fixed << setprecision(5) << burned << " " << inverse << "\n";
    return 0;
}
```

---

## 5) Python implementation with detailed comments

```python
import math
import sys

EPS = 1e-9
PI = math.acos(-1.0)

class Point:
    __slots__ = ("x", "y")
    def __init__(self, x=0.0, y=0.0):
        self.x = float(x)
        self.y = float(y)

    def __add__(self, o): return Point(self.x + o.x, self.y + o.y)
    def __sub__(self, o): return Point(self.x - o.x, self.y - o.y)
    def __mul__(self, k): return Point(self.x * k, self.y * k)

    def norm(self) -> float:
        return math.hypot(self.x, self.y)

    def unit(self):
        n = self.norm()
        return Point(self.x / n, self.y / n)

    def perp(self):
        return Point(-self.y, self.x)

    def angle(self) -> float:
        return math.atan2(self.y, self.x)

def arc_area(center: Point, r: float, p1: Point, p2: Point) -> float:
    """
    Signed area contribution of CCW circular arc from p1 to p2 on circle (center, r),
    using Green's theorem closed form.
    """
    t1 = (p1 - center).angle()
    t2 = (p2 - center).angle()
    if t2 < t1 - EPS:
        t2 += 2.0 * PI

    cx, cy = center.x, center.y
    area = r * cx * (math.sin(t2) - math.sin(t1)) \
         - r * cy * (math.cos(t2) - math.cos(t1)) \
         + r * r  * (t2 - t1)
    return 0.5 * area

def intersect_circles(c1: Point, r1: float, c2: Point, r2: float):
    """
    Return 0/1/2 intersection points of circles (c1,r1) and (c2,r2).
    """
    d = c2 - c1
    dist = d.norm()

    # No intersection (separate, contained), or same center
    if dist > r1 + r2 + EPS: return []
    if dist < abs(r1 - r2) - EPS: return []
    if dist < EPS: return []

    a = (r1*r1 - r2*r2 + dist*dist) / (2.0 * dist)
    h2 = r1*r1 - a*a
    if h2 < -EPS:
        return []
    if h2 < 0.0:
        h2 = 0.0
    h = math.sqrt(h2)

    mid = c1 + d.unit() * a
    perp_dir = d.perp().unit()

    if h < EPS:
        return [mid]
    return [mid + perp_dir * h, mid - perp_dir * h]

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))

    centers = []
    radii = []
    for _ in range(n):
        x = float(next(it)); y = float(next(it)); r = float(next(it))
        centers.append(Point(x, y))
        radii.append(r)

    # events[i] = list of (angle, point) on circle i
    events = [[] for _ in range(n)]

    for i in range(n):
        c = centers[i]
        r = radii[i]

        # Two guaranteed points on circle
        right = c + Point(r, 0.0)
        left  = c - Point(r, 0.0)
        events[i].append(((right - c).angle(), right))
        events[i].append(((left  - c).angle(), left))

        # All intersections with other circles
        for j in range(n):
            if i == j: 
                continue
            for p in intersect_circles(c, r, centers[j], radii[j]):
                events[i].append(((p - c).angle(), p))

        # Sort by angle and deduplicate by angle
        events[i].sort(key=lambda t: t[0])
        uniq = []
        for ang, p in events[i]:
            if not uniq or abs(uniq[-1][0] - ang) > EPS:
                uniq.append((ang, p))
        events[i] = uniq

    def count_circles(p: Point) -> int:
        """Count how many circles strictly contain point p."""
        cnt = 0
        for k in range(n):
            if (p - centers[k]).norm() < radii[k] - EPS:
                cnt += 1
        return cnt

    burned = 0.0
    inverse = 0.0

    for i in range(n):
        m = len(events[i])
        if m < 2:
            continue

        c = centers[i]
        r = radii[i]

        for j in range(m):
            ang1, p1 = events[i][j]
            ang2, p2 = events[i][(j + 1) % m]

            # unwrap angle
            if ang2 < ang1:
                ang2 += 2.0 * PI

            # mid-angle for inside/outside sampling
            mid_ang = 0.5 * (ang1 + ang2)
            dir = Point(math.cos(mid_ang), math.sin(mid_ang))

            test_in  = c + dir * (r - 1e-6)
            test_out = c + dir * (r + 1e-6)

            cnt_in = count_circles(test_in)
            cnt_out = count_circles(test_out)

            piece = arc_area(c, r, p1, p2)

            # inside side adds
            if cnt_in % 2 == 1:
                burned += piece
            elif cnt_in > 0:
                inverse += piece

            # outside side subtracts (ignore cnt==0 outer infinite region)
            if cnt_out % 2 == 1:
                burned -= piece
            elif cnt_out > 0:
                inverse -= piece

    print(f"{burned:.5f} {inverse:.5f}")

if __name__ == "__main__":
    solve()
```

This implements the arc-based Green’s theorem method: it avoids explicit planar-face construction while still summing each region’s area into the correct parity bucket.