<|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.

373. Carlsson vs. Winnie-the-Pooh
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Carlsson and Winnie the Pooh are eating one pizza, which is a circle of radius R. They divided the pizza into some pieces by N straight lines. They eat pizza in a following way. Any person takes a piece and eats it, then takes the next piece, eats it and so on. They eat pieces with the same speed. The time of eating a piece is proportional to its area. If at any moment of time they are both trying to take a piece simultaneously, Carlsson does his selection first. Your goal is to write the program, which determines the amounts of pizza eaten by each side, if it is known that both sides try to maximize their total amount of eaten pizza.

Input
The first line of the input contains N (1 ≤ N≤ 4) and R (1 ≤ R≤ 100). The center of the pizza is located at (0, 0). Each of the next N lines describes one line with three integers a, b and c (-1000 ≤ a, b, c≤ 1000). These numbers correspond to equation ax + by + c = 0. It is guaranteed that each line intersects the edge of pizza in exactly two points.

Output
Output the area of pizza eaten by Carlsson and by Winnie the Pooh. The testing program checks whether the answer is within 10-4 of the right answer.

Example(s)
sample input
sample output
1 100
1 0 0
15707.9632679490 15707.9632679490

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

A pizza is a disk of radius **R** centered at (0,0). It is cut by **N** straight lines (1 ≤ N ≤ 4), each intersects the circle in exactly two points, producing several pieces.

Carlsson and Winnie-the-Pooh repeatedly:
1) take one remaining piece,
2) eat it; eating time is proportional to the piece area (same speed for both),
3) when someone finishes, they immediately take another remaining piece.

If both become free at the same time, **Carlsson chooses first**.

Both play optimally to maximize their own total eaten area. Output final areas eaten by Carlsson and Pooh (error ≤ 1e-4).

---

## 2) Key observations

1. **Eating time equals total area already taken.**
   If Carlsson has eaten area `tc` so far and Pooh has eaten `tp`, then at any moment their "busy time" is exactly these totals.

2. **Who chooses next is determined by `tc` vs `tp`, not alternating turns.**
   - If `tc <= tp` => Carlsson is free earlier (or tie) => Carlsson picks next.
   - Else Pooh picks next.

3. **Game is not greedy.**
   Taking a huge piece can delay your next pick and allow the opponent to take multiple smaller pieces.

4. **N <= 4 => number of pieces is very small.**
   A set of N lines creates at most `1 + N(N+1)/2` regions in the plane (<= 11 for N=4). Intersecting with the disk still yields O(11) pieces.
   Therefore we can compute all piece areas and do a full minimax over subsets.

5. **We must compute exact areas of all faces formed by chords + circle boundary.**
   Use a planar graph / half-edge (DCEL-like) traversal:
   - vertices: all line-circle intersections and line-line intersections inside the disk
   - edges: chord segments between consecutive vertices on a line + circle arcs between consecutive boundary vertices
   - traverse faces via half-edge `next` pointers
   - compute area via Green's theorem (segments + arc contributions)

---

## 3) Full solution approach

### Part A - Build the arrangement inside the circle and extract piece areas

**A1) Collect vertices**
- For each line `ax + by + c = 0`, compute its two intersection points with the circle `x^2 + y^2 = R^2`.
- For each pair of lines, compute their intersection point; keep it only if it lies inside/on the disk.
- Deduplicate close points (floating precision).

**A2) Create edges**
- For each line:
  - collect all vertices that lie on it (its two circle endpoints + interior line-line intersections),
  - sort them along the line,
  - connect consecutive points with straight segment edges (chord pieces).
- For the circle boundary:
  - collect all circle intersection vertices,
  - sort them by polar angle,
  - connect consecutive vertices with **circular arc** edges in CCW order.

Represent each undirected edge as two directed **half-edges** with `twin` pointers.

**A3) Link half-edges into faces (DCEL rule)**
At each vertex, sort outgoing half-edges by direction angle (CCW).
For a half-edge `h`, define:
> `next(h)` = the outgoing half-edge at `to(h)` that is immediately **clockwise** from `twin(h)`.

This ensures face traversal keeps the face on the left side.

Walking `h -> next(h) -> next(next(h)) ...` gives one face boundary.

**A4) Compute face areas**
Use Green's theorem by summing contributions of each boundary element:

- For a **segment** from `P` to `Q`:
  `2A += cross(P, Q) = Px*Qy - Py*Qx`
- For a **circle arc** of radius `R` centered at origin from angle `theta1` to `theta2` along the arc direction:
  `2A += R^2 * delta_theta` (signed), where `delta_theta` is adjusted into `(0, 2pi]` for CCW and `[-2pi, 0)` for CW.

Faces inside the disk come out with **positive** signed area; the exterior face is negative.
Collect all `A > 0` as pizza piece areas.

---

### Part B - Solve the optimal game by minimax over subsets

Let `areas[]` be all piece areas, `p = len(areas)`.

State during play:
- `mask`: bitmask of already taken pieces
- `tc`: Carlsson total eaten area so far (also time spent)
- `tp`: Pooh total eaten area so far
- objective: maximize Carlsson's final total area

Turn rule:
- if `tc <= tp` (tie to Carlsson): Carlsson chooses next
- else Pooh chooses next

Minimax recursion:
- terminal: all taken => return Carlsson total so far
- Carlsson node: choose remaining piece i maximizing result
- Pooh node: choose remaining piece i minimizing Carlsson's result

Because `p <= ~11`, brute force (with alpha-beta pruning) is fast.

Finally:
- `carl = minimax(...)`
- `pooh = total_area - carl`

---

## 4) C++ Solution

```cpp
#include <bits/stdc++.h>
// #include <coding_library/geometry/point.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = double;

struct Point {
    static constexpr coord_t eps = 1e-9;
    static inline const coord_t PI = acos((coord_t)-1.0);

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

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }
    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }
    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    coord_t norm() const { return sqrt(norm2()); }
    coord_t angle() const { return atan2(y, x); }

    Point rotate(coord_t a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }
    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }
    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(-eps <= v && v <= eps) {
            return 0;
        } else if(v > 0) {
            return 1;
        } else {
            return -1;
        }
    }

    friend bool point_on_segment(
        const Point& a, const Point& b, const Point& p
    ) {
        return ccw(a, b, p) == 0 && p.x >= min(a.x, b.x) - eps &&
               p.x <= max(a.x, b.x) + eps && p.y >= min(a.y, b.y) - eps &&
               p.y <= max(a.y, b.y) + eps;
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }

    friend Point line_line_intersection(
        const Point& a1, const Point& b1, const Point& a2, const Point& b2
    ) {
        return a1 +
               (b1 - a1) * ((a2 - a1) ^ (b2 - a2)) / ((b1 - a1) ^ (b2 - a2));
    }

    friend bool collinear(const Point& a, const Point& b) {
        return abs(a ^ b) < eps;
    }

    friend Point circumcenter(const Point& a, const Point& b, const Point& c) {
        Point mid_ab = (a + b) / 2.0;
        Point mid_ac = (a + c) / 2.0;
        Point perp_ab = (b - a).perp();
        Point perp_ac = (c - a).perp();
        return line_line_intersection(
            mid_ab, mid_ab + perp_ab, mid_ac, mid_ac + perp_ac
        );
    }

    friend coord_t arc_area(
        const Point& center, coord_t r, const Point& p1, const Point& p2
    ) {
        coord_t theta1 = (p1 - center).angle();
        coord_t theta2 = (p2 - center).angle();
        if(theta2 < theta1 - eps) {
            theta2 += 2 * PI;
        }

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

    friend 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();

        if(dist > r1 + r2 + eps || dist < abs(r1 - r2) - eps || dist < eps) {
            return {};
        }

        coord_t a = (r1 * r1 - r2 * r2 + dist * dist) / (2 * dist);
        coord_t h_sq = r1 * r1 - a * a;
        if(h_sq < -eps) {
            return {};
        }
        if(h_sq < 0) {
            h_sq = 0;
        }
        coord_t h = sqrt(h_sq);

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

        if(h < eps) {
            return {mid};
        }
        return {mid + perp_dir * h, mid - perp_dir * h};
    }

    friend optional<Point> intersect_ray_segment(
        const Point& ray_start, const Point& ray_through, const Point& seg_a,
        const Point& seg_b
    ) {
        Point ray_dir = ray_through - ray_start;
        if(ray_dir.norm2() < Point::eps) {
            return {};
        }
        Point seg_dir = seg_b - seg_a;
        coord_t denom = ray_dir ^ seg_dir;
        if(fabs(denom) < eps) {
            return {};
        }
        coord_t t = ((seg_a - ray_start) ^ seg_dir) / denom;
        if(t < eps) {
            return {};
        }
        coord_t s = ((seg_a - ray_start) ^ ray_dir) / denom;
        if(s < eps || s > 1 - eps) {
            return {};
        }
        return ray_start + ray_dir * t;
    }
};

void read() {}

void solve() {
    // There are N <= 4 cuts, meaning that there would be at most O(N^2) pizza
    // slices corresponding to faces in the "planar" graph. We build a DCEL of
    // the arrangement: vertices are line-line and line-circle intersections,
    // edges are either straight chord pieces or circular arcs between
    // consecutive vertices on the circle. Each edge becomes two twin
    // half-edges; at every vertex we sort the outgoing half-edges CCW by
    // tangent angle and set next(h) = the outgoing half-edge immediately
    // clockwise from twin(h). Walking next-pointers yields every face exactly
    // once; areas come from Green's theorem over the boundary (straight
    // line pieces are direct, (1/2) r^2 dtheta for arcs). The unbounded
    // outer face shows up with negative area and gets dropped.
    //
    // For the game itself greedy is NOT optimal: picking a large piece keeps
    // you busy and lets the opponent grab several small pieces in a row. E.g.
    // with pieces {6,5,5,5,5}, Carlsson gets 11 by taking 6 first but 15 by
    // taking a 5 first (letting Pooh commit to the slow 6). So we run a real
    // minimax with alpha-beta, where the next mover is whoever currently has
    // the smaller cumulative eating time (ties go to Carlsson).

    int n;
    double r;
    cin >> n >> r;
    vector<array<double, 3>> lines(n);
    for(auto& l: lines) {
        cin >> l[0] >> l[1] >> l[2];
    }

    auto line_circle_pts = [&](int i) -> array<Point, 2> {
        double a = lines[i][0], b = lines[i][1], c = lines[i][2];
        double n2 = a * a + b * b;
        Point foot(-a * c / n2, -b * c / n2);
        double h2 = r * r - c * c / n2;
        double h = sqrt(max(0.0, h2));
        Point dir = Point(-b, a) / sqrt(n2);
        return {foot + dir * h, foot - dir * h};
    };

    auto line_line_pt = [&](int i, int j) -> optional<Point> {
        double a1 = lines[i][0], b1 = lines[i][1], c1 = lines[i][2];
        double a2 = lines[j][0], b2 = lines[j][1], c2 = lines[j][2];
        double d = a1 * b2 - a2 * b1;
        if(fabs(d) < Point::eps) {
            return nullopt;
        }
        Point p((-c1 * b2 + b1 * c2) / d, (-a1 * c2 + a2 * c1) / d);
        if(p.norm() > r + Point::eps) {
            return nullopt;
        }
        return p;
    };

    vector<Point> verts;
    auto add_vertex = [&](Point p) {
        for(int i = 0; i < (int)verts.size(); i++) {
            if((verts[i] - p).norm() < 1e-7) {
                return i;
            }
        }
        verts.push_back(p);
        return (int)verts.size() - 1;
    };

    struct HalfEdge {
        int from, to;
        bool is_arc;
        bool ccw;
        int twin;
        int next;
    };
    vector<HalfEdge> hes;
    auto add_edge = [&](int u, int v, bool is_arc, bool ccw_uv) {
        int h1 = (int)hes.size();
        hes.push_back({u, v, is_arc, ccw_uv, h1 + 1, -1});
        hes.push_back({v, u, is_arc, !ccw_uv, h1, -1});
    };

    for(int i = 0; i < n; i++) {
        vector<int> on_line;
        auto cp = line_circle_pts(i);
        on_line.push_back(add_vertex(cp[0]));
        on_line.push_back(add_vertex(cp[1]));
        for(int j = 0; j < n; j++) {
            if(j == i) {
                continue;
            }
            auto pt = line_line_pt(i, j);
            if(pt) {
                on_line.push_back(add_vertex(*pt));
            }
        }
        double a = lines[i][0], b = lines[i][1];
        sort(on_line.begin(), on_line.end(), [&](int u, int v) {
            return -b * verts[u].x + a * verts[u].y <
                   -b * verts[v].x + a * verts[v].y;
        });
        on_line.erase(unique(on_line.begin(), on_line.end()), on_line.end());
        for(int k = 0; k + 1 < (int)on_line.size(); k++) {
            add_edge(on_line[k], on_line[k + 1], false, false);
        }
    }

    vector<int> circle_verts;
    for(int i = 0; i < n; i++) {
        auto cp = line_circle_pts(i);
        circle_verts.push_back(add_vertex(cp[0]));
        circle_verts.push_back(add_vertex(cp[1]));
    }
    auto angle_of = [&](int v) {
        double a = atan2(verts[v].y, verts[v].x);
        if(a < 0) {
            a += 2 * Point::PI;
        }
        return a;
    };
    sort(circle_verts.begin(), circle_verts.end(), [&](int u, int v) {
        return angle_of(u) < angle_of(v);
    });
    circle_verts.erase(
        unique(circle_verts.begin(), circle_verts.end()), circle_verts.end()
    );
    int cm = (int)circle_verts.size();
    for(int k = 0; k < cm; k++) {
        add_edge(circle_verts[k], circle_verts[(k + 1) % cm], true, true);
    }

    auto outgoing_dir = [&](int h) -> Point {
        Point p = verts[hes[h].from];
        if(!hes[h].is_arc) {
            return verts[hes[h].to] - p;
        }
        return hes[h].ccw ? Point(-p.y, p.x) : Point(p.y, -p.x);
    };

    int vtotal = (int)verts.size();
    vector<vector<int>> out_at(vtotal);
    for(int h = 0; h < (int)hes.size(); h++) {
        out_at[hes[h].from].push_back(h);
    }
    for(auto& lst: out_at) {
        sort(lst.begin(), lst.end(), [&](int a, int b) {
            Point da = outgoing_dir(a);
            Point db = outgoing_dir(b);
            return atan2(da.y, da.x) < atan2(db.y, db.x);
        });
    }
    vector<int> pos_of(hes.size());
    for(int v = 0; v < vtotal; v++) {
        for(int k = 0; k < (int)out_at[v].size(); k++) {
            pos_of[out_at[v][k]] = k;
        }
    }
    for(int h = 0; h < (int)hes.size(); h++) {
        int t = hes[h].twin;
        int v = hes[t].from;
        int k = (int)out_at[v].size();
        hes[h].next = out_at[v][(pos_of[t] - 1 + k) % k];
    }

    vector<bool> visited(hes.size(), false);
    vector<double> areas;
    for(int h0 = 0; h0 < (int)hes.size(); h0++) {
        if(visited[h0]) {
            continue;
        }
        double area2 = 0;
        int cur = h0;
        while(!visited[cur]) {
            visited[cur] = true;
            Point pf = verts[hes[cur].from];
            Point pt = verts[hes[cur].to];
            if(!hes[cur].is_arc) {
                area2 += pf.x * pt.y - pt.x * pf.y;
            } else {
                double th1 = atan2(pf.y, pf.x);
                double th2 = atan2(pt.y, pt.x);
                double dth = th2 - th1;
                if(hes[cur].ccw) {
                    if(dth <= 1e-12) {
                        dth += 2 * Point::PI;
                    }
                } else {
                    if(dth >= -1e-12) {
                        dth -= 2 * Point::PI;
                    }
                }
                area2 += r * r * dth;
            }
            cur = hes[cur].next;
        }
        double a = area2 / 2.0;
        if(a > 1e-9) {
            areas.push_back(a);
        }
    }

    int p = (int)areas.size();
    function<double(int, double, double, double, double, double)>
        best_carlsson = [&](int mask, double tc, double tp, double csf,
                            double alpha, double beta) -> double {
        if(mask == (1 << p) - 1) {
            return csf;
        }
        bool c_turn = (tc <= tp + Point::eps);
        if(c_turn) {
            double best = -1e18;
            for(int i = 0; i < p; i++) {
                if(mask & (1 << i)) {
                    continue;
                }
                double v = best_carlsson(
                    mask | (1 << i), tc + areas[i], tp, csf + areas[i], alpha,
                    beta
                );
                best = max(best, v);
                alpha = max(alpha, best);
                if(alpha >= beta) {
                    break;
                }
            }
            return best;
        } else {
            double best = 1e18;
            for(int i = 0; i < p; i++) {
                if(mask & (1 << i)) {
                    continue;
                }
                double v = best_carlsson(
                    mask | (1 << i), tc, tp + areas[i], csf, alpha, beta
                );
                best = min(best, v);
                beta = min(beta, best);
                if(alpha >= beta) {
                    break;
                }
            }
            return best;
        }
    };

    double total = 0;
    for(double a: areas) {
        total += a;
    }
    double carlsson = best_carlsson(0, 0, 0, 0, -1e18, 1e18);
    double pooh = total - carlsson;
    cout << fixed << setprecision(10) << carlsson << ' ' << pooh << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python Solution (same approach, detailed comments)

```python
import math
from typing import List, Tuple, Optional

EPS = 1e-9
PI = math.pi

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

    def __add__(self, other): return Point(self.x + other.x, self.y + other.y)
    def __sub__(self, other): return Point(self.x - other.x, self.y - other.y)
    def __mul__(self, c: float): return Point(self.x * c, self.y * c)
    def __truediv__(self, c: float): return Point(self.x / c, self.y / c)

    def dot(self, other) -> float: return self.x * other.x + self.y * other.y
    def cross(self, other) -> float: return self.x * other.y - self.y * other.x

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

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

    def unit(self):
        n = self.norm()
        return self / n

def atan2pi(y: float, x: float) -> float:
    """Angle in [0, 2pi)."""
    a = math.atan2(y, x)
    if a < 0:
        a += 2 * PI
    return a

class HalfEdge:
    __slots__ = ("frm", "to", "is_arc", "ccw", "twin", "nxt")
    def __init__(self, frm: int, to: int, is_arc: bool, ccw: bool, twin: int):
        self.frm = frm
        self.to = to
        self.is_arc = is_arc
        self.ccw = ccw
        self.twin = twin
        self.nxt = -1

def solve() -> None:
    import sys
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    r = float(next(it))

    lines: List[Tuple[float, float, float]] = []
    for _ in range(n):
        a = float(next(it)); b = float(next(it)); c = float(next(it))
        lines.append((a, b, c))

    def line_circle_pts(i: int) -> Tuple[Point, Point]:
        a, b, c = lines[i]
        n2 = a*a + b*b
        foot = Point(-a*c/n2, -b*c/n2)
        h2 = r*r - (c*c)/n2
        if h2 < 0:
            h2 = 0.0
        h = math.sqrt(h2)
        dirv = Point(-b, a) / math.sqrt(n2)
        return foot + dirv*h, foot - dirv*h

    def line_line_pt(i: int, j: int) -> Optional[Point]:
        a1, b1, c1 = lines[i]
        a2, b2, c2 = lines[j]
        d = a1*b2 - a2*b1
        if abs(d) < EPS:
            return None
        x = (-c1*b2 + b1*c2) / d
        y = (-a1*c2 + a2*c1) / d
        p = Point(x, y)
        if p.norm() > r + EPS:
            return None
        return p

    verts: List[Point] = []

    def add_vertex(p: Point) -> int:
        for idx, q in enumerate(verts):
            if (q - p).norm() < 1e-7:
                return idx
        verts.append(p)
        return len(verts) - 1

    hes: List[HalfEdge] = []

    def add_edge(u: int, v: int, is_arc: bool, ccw_uv: bool) -> None:
        h1 = len(hes)
        hes.append(HalfEdge(u, v, is_arc, ccw_uv, h1 + 1))
        hes.append(HalfEdge(v, u, is_arc, not ccw_uv, h1))

    for i in range(n):
        on_line: List[int] = []
        p1, p2 = line_circle_pts(i)
        on_line.append(add_vertex(p1))
        on_line.append(add_vertex(p2))
        for j in range(n):
            if j == i:
                continue
            p = line_line_pt(i, j)
            if p is not None:
                on_line.append(add_vertex(p))

        a, b, _ = lines[i]
        on_line.sort(key=lambda vid: (-b)*verts[vid].x + a*verts[vid].y)

        uniq = []
        last = None
        for vid in on_line:
            if last is None or vid != last:
                uniq.append(vid)
            last = vid
        on_line = uniq

        for k in range(len(on_line) - 1):
            add_edge(on_line[k], on_line[k+1], is_arc=False, ccw_uv=False)

    circle_verts: List[int] = []
    for i in range(n):
        p1, p2 = line_circle_pts(i)
        circle_verts.append(add_vertex(p1))
        circle_verts.append(add_vertex(p2))

    circle_verts.sort(key=lambda vid: atan2pi(verts[vid].y, verts[vid].x))
    uniq = []
    last = None
    for vid in circle_verts:
        if last is None or vid != last:
            uniq.append(vid)
        last = vid
    circle_verts = uniq

    m = len(circle_verts)
    for k in range(m):
        add_edge(circle_verts[k], circle_verts[(k+1) % m], is_arc=True, ccw_uv=True)

    def outgoing_dir(h: int) -> Point:
        p = verts[hes[h].frm]
        if not hes[h].is_arc:
            return verts[hes[h].to] - p
        if hes[h].ccw:
            return Point(-p.y, p.x)
        else:
            return Point(p.y, -p.x)

    out_at: List[List[int]] = [[] for _ in range(len(verts))]
    for h in range(len(hes)):
        out_at[hes[h].frm].append(h)

    for v in range(len(verts)):
        out_at[v].sort(key=lambda h: math.atan2(outgoing_dir(h).y, outgoing_dir(h).x))

    pos_of = [0] * len(hes)
    for v in range(len(verts)):
        for k, h in enumerate(out_at[v]):
            pos_of[h] = k

    for h in range(len(hes)):
        t = hes[h].twin
        v = hes[t].frm
        k = len(out_at[v])
        hes[h].nxt = out_at[v][(pos_of[t] - 1) % k]

    visited = [False] * len(hes)
    areas: List[float] = []

    for h0 in range(len(hes)):
        if visited[h0]:
            continue
        area2 = 0.0
        cur = h0
        while not visited[cur]:
            visited[cur] = True
            pf = verts[hes[cur].frm]
            pt = verts[hes[cur].to]

            if not hes[cur].is_arc:
                area2 += pf.x * pt.y - pt.x * pf.y
            else:
                th1 = math.atan2(pf.y, pf.x)
                th2 = math.atan2(pt.y, pt.x)
                dth = th2 - th1
                if hes[cur].ccw:
                    if dth <= 1e-12:
                        dth += 2 * PI
                else:
                    if dth >= -1e-12:
                        dth -= 2 * PI
                area2 += r * r * dth

            cur = hes[cur].nxt

        a = area2 / 2.0
        if a > 1e-9:
            areas.append(a)

    p = len(areas)

    sys.setrecursionlimit(10000)

    def best_carlsson(mask: int, tc: float, tp: float, csf: float,
                      alpha: float, beta: float) -> float:
        if mask == (1 << p) - 1:
            return csf

        c_turn = (tc <= tp + EPS)

        if c_turn:
            best = -1e100
            for i in range(p):
                if mask & (1 << i):
                    continue
                v = best_carlsson(mask | (1 << i),
                                  tc + areas[i], tp,
                                  csf + areas[i],
                                  alpha, beta)
                if v > best:
                    best = v
                if best > alpha:
                    alpha = best
                if alpha >= beta:
                    break
            return best
        else:
            best = 1e100
            for i in range(p):
                if mask & (1 << i):
                    continue
                v = best_carlsson(mask | (1 << i),
                                  tc, tp + areas[i],
                                  csf,
                                  alpha, beta)
                if v < best:
                    best = v
                if best < beta:
                    beta = best
                if alpha >= beta:
                    break
            return best

    total = sum(areas)
    carl = best_carlsson(0, 0.0, 0.0, 0.0, -1e100, 1e100)
    pooh = total - carl

    sys.stdout.write(f"{carl:.10f} {pooh:.10f}\n")

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