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

312. 4-3 King
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The king of the Quadroland (or was it Triland?..) has died. After four or three days of mourning, his will was declared: all his kingdom was to be divided into four or three parts, one for each son. The kingdom itself can be represented as a quadrangle or a triangle on a plane, with each side associated with one of the sons. After the division is performed, each son should get a quadrangle or a triangle, one of the sides coinciding with his associated side of the original kingdom. The required ratio between areas of their parts is given. You are to perform such a division.

Input
The first line of the input file contains the number N (3 ≤ N ≤ 4) of sons (equal to the number of sides of the kingdom).

The next N lines contain the coordinates of the vertices of the kingdom. The vertices are given in either clockwise or counter-clockwise order. No two consecutive sides of the kingdom lie on the same line. Each coordinate is an integer not exceeding 100 by its absolute value.

The last, (N+2)-th line contains the required ratio formatted like K1:K2:...:KN, where K1 corresponds to the side between 1st and 2nd vertices, K2 — between 2nd and 3rd vertices, etc, KN — between Nth and 1st vertices. Each Ki is an integer, 1 ≤ Ki ≤ 100.

Output
The first line of the output file should contain the description of the part corresponding to the side between 1st and 2nd vertices, the second line — between 2nd and 3rd vertices, etc.

Each description should consist of the number of vertices in the polygon (3 or 4), followed by their coordinates, in either clockwise or counter-clockwise order. Two ends of each side should be some neighbouring vertices of the corresponding polygon. The coordinates can be real numbers; if this is the case, print as many digits after the decimal point as possible.

In case the division is impossible, output -1 on the only line of output.

Example(s)
sample input
sample output
3
0 0
10 0
0 10
4:2:4
3 0 0 10 0 4 4
3 10 0 0 10 4 4
3 0 10 0 0 4 4

sample input
sample output
4
0 0
0 30
100 30
100 0
1:3:1:3
3 0 0 0 30 25.0 15.0
4 0 30 100 30 75.0 15.0 25.0 15.0
3 100 30 100 0 75.0 15.0
4 0 0 100 0 75.0 15.0 25.0 15.0

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

You are given a polygon with **N = 3 or N = 4** vertices (triangle or quadrilateral) in clockwise or counterclockwise order. Each side is assigned to one son, and a ratio `K1:K2:...:KN` is given (side `i` is between vertex `i` and `i+1`, wrapping around).

Partition the polygon into **N parts**, each part being a **triangle or quadrilateral**, such that:

- Part `i` has an edge coinciding with the **original side i**.
- The areas of the parts are in ratio `K1:K2:...:KN`.

Output the `N` polygons in order of sides. If impossible, output `-1`.

---

## 2) Key observations

### Geometry facts
1. **Signed triangle area**:
   \[
   \text{area}(A,B,C)=\frac12\left((B-A)\times(C-A)\right)
   \]
   (cross product in 2D). Using **signed** areas makes formulas consistent regardless of CW/CCW input.

2. **Linearity along a segment**:  
   If \(P\) moves along segment \(XY\), then \(\text{area}(A,X,P)\) changes **linearly** with the interpolation parameter.  
   This lets us pick points on edges/diagonals to match exact area ratios by simple interpolation.

### Structural insights
3. **N = 3 (triangle)** is always solvable by choosing one interior point \(O\) and splitting into 3 triangles \((ABO),(BCO),(CAO)\). Barycentric coordinates give a direct formula for \(O\).

4. **N = 4 (quadrilateral)**: at least one diagonal (either \(AC\) or \(BD\)) lies inside the quadrilateral (including simple concave “arrow” cases). We can:
   - choose an internal diagonal,
   - pick a point \(Q\) on that diagonal so that it splits the total area in ratio \((K_1+K_4):(K_2+K_3)\) (or similarly for \(BD\)),
   - then solve two independent “split a quadrilateral into two pieces with given ratio” subproblems.

---

## 3) Full solution approach

Let the input polygon be \(P_0,P_1,\dots,P_{N-1}\) and ratios \(K_0,\dots,K_{N-1}\) corresponding to sides \((P_i,P_{i+1})\).

### Case A: N = 3 (triangle)
Let \(A=P_0, B=P_1, C=P_2\), ratios \(K_1,K_2,K_3\) correspond to sides \(AB,BC,CA\) respectively (0-based: \(K_0,K_1,K_2\)).

We want:
- region for side \(AB\): triangle \(A,B,O\)
- region for side \(BC\): triangle \(B,C,O\)
- region for side \(CA\): triangle \(C,A,O\)

Using barycentric coordinates, if:
\[
O = \frac{K_{BC}\cdot A + K_{CA}\cdot B + K_{AB}\cdot C}{K_{AB}+K_{BC}+K_{CA}}
\]
(i.e. \(O=\frac{K_1A+K_2B+K_0C}{K_0+K_1+K_2}\) in 0-based)
then:
\[
[ABO]:[BCO]:[CAO] = K_{AB}:K_{BC}:K_{CA}
\]
So we can output the three triangles directly.

### Case B: N = 4 (quadrilateral)
Let \(A=P_0,B=P_1,C=P_2,D=P_3\), ratios \(K_0,K_1,K_2,K_3\) for sides \(AB,BC,CD,DA\).

#### Step 1: choose an internal diagonal
Check whether \(B\) and \(D\) are on opposite sides of line \(AC\):
- compute \(s_1 = ccw(A,C,B)\), \(s_2 = ccw(A,C,D)\)
- if \(s_1\cdot s_2 < 0\), use diagonal **AC**, else use **BD**.

#### Step 2: choose point Q on the diagonal to match the *sum* ratios
If using diagonal **AC**, we want area on the “A-side” (parts for \(AB\) and \(DA\)) to be \((K_0+K_3)/\sum K\) of total. Because area varies linearly along the diagonal, we can take:
\[
t=\frac{K_0+K_3}{K_0+K_1+K_2+K_3},\quad Q = A + t(C-A)
\]
Then the quadrilateral is split into two quadrilaterals:
- \(A,B,Q,D\) with combined ratio \(K_0:K_3\)
- \(C,D,Q,B\) with combined ratio \(K_2:K_1\) (note the order we’ll pass)

If using diagonal **BD**, similarly:
\[
t=\frac{K_0+K_1}{\sum K},\quad Q = B + t(D-B)
\]
producing:
- \(B,C,Q,A\) for \(K_1:K_0\)
- \(D,A,Q,C\) for \(K_3:K_2\)

#### Step 3: splitting a quadrilateral into two parts with given ratio (helper)
We need a function:

`split_quad(v0,v1,v2,v3, r1,r2)`

Vertices are in order around the quadrilateral. We will cut from vertex `v0` to a point `P` on the chain `v1 -> v2 -> v3` so that:
- part1 has side `v0v1` and area ratio `r1`
- part2 has side `v3v0` and area ratio `r2`

Compute:
- \(a_1 = [v0,v1,v2]\)
- \(a_2 = [v0,v2,v3]\)
- total \(= a_1+a_2\)
- target \(= \frac{r1}{r1+r2}\cdot total\)

If `target` is within the first triangle, `P` lies on segment `v1v2` at fraction \(s=target/a_1\).  
Else it lies on `v2v3` at fraction \(s=(target-a_1)/a_2\).  
Then output either (triangle + quad) or (quad + triangle). This uses linearity of area along a segment.

#### Output ordering
Finally, assemble the 4 regions in the order for sides:
1. side \(AB\) (K0)
2. side \(BC\) (K1)
3. side \(CD\) (K2)
4. side \(DA\) (K3)

**Impossibility**: Under typical constraints for this problem (simple quadrilateral with no collinear adjacent edges), this construction works. If you want to be defensive, you can detect degenerate zero areas and print `-1`, but the standard accepted approach doesn’t need it.

---

## 4) C++ Solution

```cpp
#include <bits/stdc++.h>
#include <vector>
// #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};
    }
};

int n;
vector<Point> pnts;
string k_ratios;

vector<int> parse_ratios(const string& s) {
    vector<int> res;
    int cur = 0;
    for(char c: s) {
        if(c == ':') {
            res.push_back(cur);
            cur = 0;
        } else {
            cur = cur * 10 + (c - '0');
        }
    }
    res.push_back(cur);
    return res;
}

double tri_area(const Point& a, const Point& b, const Point& c) {
    return 0.5 * ((b - a) ^ (c - a));
}

struct Region {
    int cnt;
    Point p[4];
};

Region make_tri(Point a, Point b, Point c) {
    Region r;
    r.cnt = 3;
    r.p[0] = a;
    r.p[1] = b;
    r.p[2] = c;
    return r;
}

Region make_quad(Point a, Point b, Point c, Point d) {
    Region r;
    r.cnt = 4;
    r.p[0] = a;
    r.p[1] = b;
    r.p[2] = c;
    r.p[3] = d;
    return r;
}

void print_region(const Region& r) {
    cout << r.cnt;
    for(int i = 0; i < r.cnt; i++) {
        cout << ' ' << r.p[i];
    }
    cout << '\n';
}

pair<Region, Region> split_quad(
    Point v0, Point v1, Point v2, Point v3, double r1, double r2
) {
    double a1 = tri_area(v0, v1, v2);
    double a2 = tri_area(v0, v2, v3);
    double total = a1 + a2;
    double target = r1 / (r1 + r2) * total;

    double s = target / a1;
    if(s >= -1e-9 && s <= 1 + 1e-9) {
        s = max(0.0, min(1.0, s));
        Point P = v1 + (v2 - v1) * s;
        return {make_tri(v0, v1, P), make_quad(v0, P, v2, v3)};
    } else {
        double rem = target - a1;
        double s2 = rem / a2;
        s2 = max(0.0, min(1.0, s2));
        Point P = v2 + (v3 - v2) * s2;
        return {make_quad(v0, v1, v2, P), make_tri(v0, P, v3)};
    }
}

void read() {
    cin >> n;
    pnts.resize(n);
    cin >> pnts >> k_ratios;
}

void solve() {
    // On first glance the problem looks very complicated, but it's actually a
    // combination of some fairly simple ideas. Let us solve the N=3 and N=4
    // cases separately.
    //
    // For N=3, it turns out it's always possible. Let's try to make the 3 areas
    // fully match with one side of the original triangle. We will denote the 3
    // vertices of the original area as A, B and C. Take the AB side. Then
    // project C onto AB to get H. The area of the triangle is CH*AB/2. We know
    // K1:K2:K3, so it's not hard to see that we would like the "height" to be
    // h1 = K1:(K2+K3) * CH. This gives us a line for potential candidate of
    // where the last point of the AB region would be (parallel line to AB at
    // distance h1). Let's repeat absolutely the same for BC. This gives us a
    // another line at distance h2 = K2:(K1+K3) * AQ, where Q is the projection
    // of A onto BC. We now have two lines, and we would like to take a point
    // that is on both so we can just intersect them (denote as O). We could do
    // a third line in the same style for CA, but two lines are already enough
    // to find O, and they guarantee that the third area will have K3:(K1+K2) as
    // the proportion.
    //
    // The N=4 case is a bit harder. Note that the polygon could be non-convex
    // (arrow-like case). Having solved N=3, we should think of a similar style
    // approach that isn't over-complicated. We will use A, B, C, and D as the
    // points. The key is that one of the two diagonals (either AC or BD), is
    // inside of the polygon. Let's use AC as the diagonal, and choose a point Q
    // on the diagonal such that the ABQD polygon compared to BCDQ has ratio
    // (K1+K4):(K2+K3). This works because area scales linearly along the
    // diagonal. Now we have two independent and simpler problems - given a
    // quadrangle, split it into two parts given two ratios. For ABQD, sides AB
    // and DA share vertex A, so we draw a line from A to a point P on the
    // opposite chain B->Q->D. We compute the target area for the AB region as
    // K1/(K1+K4) * area(ABQD). If P lies on segment BQ at fraction s, then
    // area(ABP) = s * area(ABQ) (since the cross product scales linearly in P).
    // So if target <= area(ABQ), we get s = target/area(ABQ) and P = B+s*(Q-B),
    // giving triangle ABP for K1 and quad APQD for K4. Otherwise P is on QD,
    // and we solve s = (target - area(ABQ)) / area(AQD) analogously, giving
    // quad ABQP for K1 and triangle APD for K4. Similarly for BCDQ, sides BC
    // and CD share vertex C, so we split from C to a point on chain D->Q->B.

    vector<int> K = parse_ratios(k_ratios);
    cout << fixed << setprecision(10);

    if(n == 3) {
        Point A = pnts[0], B = pnts[1], C = pnts[2];
        double sum = K[0] + K[1] + K[2];
        Point O = (A * K[1] + B * K[2] + C * K[0]) / sum;
        cout << "3 " << A << ' ' << B << ' ' << O << '\n';
        cout << "3 " << B << ' ' << C << ' ' << O << '\n';
        cout << "3 " << C << ' ' << A << ' ' << O << '\n';
    } else {
        Point A = pnts[0], B = pnts[1], C = pnts[2], D = pnts[3];
        double sum = K[0] + K[1] + K[2] + K[3];

        int s1 = ccw(A, C, B), s2 = ccw(A, C, D);

        Region r[4];
        if(s1 * s2 < 0) {
            double t = (K[0] + K[3]) / sum;
            Point Q = A + (C - A) * t;
            auto [r0, r3] = split_quad(A, B, Q, D, K[0], K[3]);
            auto [r2, r1] = split_quad(C, D, Q, B, K[2], K[1]);
            r[0] = r0;
            r[1] = r1;
            r[2] = r2;
            r[3] = r3;
        } else {
            double t = (K[0] + K[1]) / sum;
            Point Q = B + (D - B) * t;
            auto [r1, r0] = split_quad(B, C, Q, A, K[1], K[0]);
            auto [r3, r2] = split_quad(D, A, Q, C, K[3], K[2]);
            r[0] = r0;
            r[1] = r1;
            r[2] = r2;
            r[3] = r3;
        }

        for(int i = 0; i < 4; i++) {
            print_region(r[i]);
        }
    }
}

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 implementation (with detailed comments)

```python
import sys
from dataclasses import dataclass
from typing import List, Tuple

EPS = 1e-9

@dataclass
class Point:
    x: float
    y: float

    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: float): return Point(self.x * k, self.y * k)   # scalar
    def __truediv__(self, k: float): return Point(self.x / k, self.y / k)

def cross(a: Point, b: Point) -> float:
    return a.x * b.y - a.y * b.x

def ccw(a: Point, b: Point, c: Point) -> int:
    v = cross(b - a, c - a)
    if -EPS <= v <= EPS:
        return 0
    return 1 if v > 0 else -1

def tri_area(a: Point, b: Point, c: Point) -> float:
    """Signed area of triangle (a,b,c)."""
    return 0.5 * cross(b - a, c - a)

def parse_ratios(s: str) -> List[int]:
    return list(map(int, s.strip().split(":")))

# Region: (count, [points...])
Region = Tuple[int, List[Point]]

def make_tri(a: Point, b: Point, c: Point) -> Region:
    return (3, [a, b, c])

def make_quad(a: Point, b: Point, c: Point, d: Point) -> Region:
    return (4, [a, b, c, d])

def split_quad(v0: Point, v1: Point, v2: Point, v3: Point,
               r1: float, r2: float) -> Tuple[Region, Region]:
    """
    Split quadrilateral v0-v1-v2-v3 into two parts with area ratio r1:r2.
    The cut is from v0 to some point P on chain v1->v2->v3.

    Returns (part_using_side v0v1, part_using_side v3v0).
    """
    a1 = tri_area(v0, v1, v2)
    a2 = tri_area(v0, v2, v3)
    total = a1 + a2
    target = (r1 / (r1 + r2)) * total

    # Try placing P on segment v1->v2
    s = target / a1
    if -1e-9 <= s <= 1 + 1e-9:
        s = max(0.0, min(1.0, s))
        P = v1 + (v2 - v1) * s
        return make_tri(v0, v1, P), make_quad(v0, P, v2, v3)

    # Otherwise P is on segment v2->v3
    rem = target - a1
    s2 = rem / a2
    s2 = max(0.0, min(1.0, s2))
    P = v2 + (v3 - v2) * s2
    return make_quad(v0, v1, v2, P), make_tri(v0, P, v3)

def fmt_point(p: Point) -> str:
    # "as many digits as possible" -> print plenty
    return f"{p.x:.10f} {p.y:.10f}"

def print_region(r: Region) -> str:
    cnt, pts = r
    return " ".join([str(cnt)] + [fmt_point(p) for p in pts])

def solve(inp: str) -> str:
    tokens = inp.strip().split()
    it = iter(tokens)

    n = int(next(it))
    pts = [Point(float(next(it)), float(next(it))) for _ in range(n)]
    ratio_str = next(it)
    K = parse_ratios(ratio_str)

    out: List[str] = []

    if n == 3:
        A, B, C = pts
        s = K[0] + K[1] + K[2]

        # O = (K_BC*A + K_CA*B + K_AB*C) / sum
        O = (A * K[1] + B * K[2] + C * K[0]) / s

        out.append(print_region(make_tri(A, B, O)))  # AB
        out.append(print_region(make_tri(B, C, O)))  # BC
        out.append(print_region(make_tri(C, A, O)))  # CA
        return "\n".join(out)

    # n == 4
    A, B, C, D = pts
    s = sum(K)
    ans: List[Region] = [None] * 4  # type: ignore

    # Choose diagonal: if B and D are on opposite sides of AC, use AC.
    s1 = ccw(A, C, B)
    s2 = ccw(A, C, D)

    if s1 * s2 < 0:
        # Use AC
        t = (K[0] + K[3]) / s
        Q = A + (C - A) * t

        r0, r3 = split_quad(A, B, Q, D, K[0], K[3])   # AB, DA
        r2, r1 = split_quad(C, D, Q, B, K[2], K[1])   # CD, BC

        ans[0], ans[1], ans[2], ans[3] = r0, r1, r2, r3
    else:
        # Use BD
        t = (K[0] + K[1]) / s
        Q = B + (D - B) * t

        r1, r0 = split_quad(B, C, Q, A, K[1], K[0])   # BC, AB
        r3, r2 = split_quad(D, A, Q, C, K[3], K[2])   # DA, CD

        ans[0], ans[1], ans[2], ans[3] = r0, r1, r2, r3

    return "\n".join(print_region(r) for r in ans)

if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()))
```

--- 

If you want, I can also add a small numeric verification routine (compute each output region’s area and check the ratio) to help debug locally—disabled for submission.