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

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

static const double EPS = 1e-9;

struct Point {
    double x, y;
    Point(double x_=0, double 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 * (double k)     const { return Point(x * k, y * k); }
    Point operator / (double k)     const { return Point(x / k, y / k); }
};

static double cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

// ccw sign of (a,b,c): +1 ccw, 0 collinear, -1 cw
static int ccw(const Point& a, const Point& b, const Point& c) {
    double v = cross(b - a, c - a);
    if (fabs(v) <= EPS) return 0;
    return (v > 0) ? 1 : -1;
}

// Signed area of triangle (a,b,c)
static double tri_area(const Point& a, const Point& b, const Point& c) {
    return 0.5 * cross(b - a, c - a);
}

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

static 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;
}

static 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;
}

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

// Parse "K1:K2:...:KN"
static 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;
}

/*
  Split quadrilateral v0-v1-v2-v3 into two regions with area ratio r1:r2.
  Cut is from v0 to some point P on chain v1->v2->v3.

  Returns (part_for_side_v0v1, part_for_side_v3v0).
*/
static 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;

    // If degenerate, the construction is unsafe (not expected in valid tests).
    // You could handle it by printing -1 in main.
    double target = (r1 / (r1 + r2)) * total;

    // Try point P on segment v1->v2:
    double s = target / a1;
    if (s >= -1e-9 && s <= 1 + 1e-9) {
        s = max(0.0, min(1.0, s));          // clamp for numerical stability
        Point P = v1 + (v2 - v1) * s;
        Region part1 = make_tri(v0, v1, P);
        Region part2 = make_quad(v0, P, v2, v3);
        return {part1, part2};
    }

    // Otherwise point P on segment v2->v3:
    double rem = target - a1;
    double s2 = rem / a2;
    s2 = max(0.0, min(1.0, s2));
    Point P = v2 + (v3 - v2) * s2;

    Region part1 = make_quad(v0, v1, v2, P);
    Region part2 = make_tri(v0, P, v3);
    return {part1, part2};
}

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

    int N;
    cin >> N;
    vector<Point> P(N);
    for (int i = 0; i < N; i++) cin >> P[i].x >> P[i].y;

    string ratio_str;
    cin >> ratio_str;
    vector<int> K = parse_ratios(ratio_str);

    cout << fixed << setprecision(10);

    if (N == 3) {
        // Triangle: A,B,C
        Point A = P[0], B = P[1], C = P[2];
        double sum = K[0] + K[1] + K[2];

        // Barycentric construction:
        // O = (K_BC*A + K_CA*B + K_AB*C) / sum
        Point O = (A * K[1] + B * K[2] + C * K[0]) / sum;

        print_region(make_tri(A, B, O)); // side AB
        print_region(make_tri(B, C, O)); // side BC
        print_region(make_tri(C, A, O)); // side CA
        return 0;
    }

    // N == 4
    Point A = P[0], B = P[1], C = P[2], D = P[3];
    double sum = K[0] + K[1] + K[2] + K[3];

    Region ans[4];

    // Decide which diagonal is inside: try AC.
    int s1 = ccw(A, C, B);
    int s2 = ccw(A, C, D);

    if (s1 * s2 < 0) {
        // Use diagonal AC. Choose Q on AC such that
        // combined area ratio near A is (K0+K3)/sum.
        double t = (K[0] + K[3]) / sum;
        Point Q = A + (C - A) * t;

        // Split ABQD into K0 (AB) and K3 (DA)
        auto [r0, r3] = split_quad(A, B, Q, D, K[0], K[3]);

        // Split CDQB around C into K2 (CD) and K1 (BC)
        // Note: we call split_quad(C, D, Q, B, K2, K1),
        // it returns (for CD, for BC) in that order.
        auto [r2, r1] = split_quad(C, D, Q, B, K[2], K[1]);

        ans[0] = r0; // AB
        ans[1] = r1; // BC
        ans[2] = r2; // CD
        ans[3] = r3; // DA
    } else {
        // Use diagonal BD. Choose Q on BD such that
        // combined ratio near B is (K0+K1)/sum.
        double t = (K[0] + K[1]) / sum;
        Point Q = B + (D - B) * t;

        // Split BCQA into K1 (BC) and K0 (AB):
        auto [r1, r0] = split_quad(B, C, Q, A, K[1], K[0]);

        // Split DAQC into K3 (DA) and K2 (CD):
        auto [r3, r2] = split_quad(D, A, Q, C, K[3], K[2]);

        ans[0] = r0; // AB
        ans[1] = r1; // BC
        ans[2] = r2; // CD
        ans[3] = r3; // DA
    }

    for (int i = 0; i < 4; i++) print_region(ans[i]);
    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.