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

209. Areas
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Consider N different lines on the plane. They divide it to several parts,some of which are finite, some infinite.

Your task in this problem is for each finite part to find its area.

Input

The first line of the input file contains N — the number of lines (1 ≤ N ≤ 80). Each of next N lines contains four integer numbers x1, y1, x2 and y2 — the coordinates of two different points of the line.

All coordinates do not exceed 102 by their absolute value.

No two lines coincide.

Output

First output K — the number of finite parts among those the lines divide the plane to.

Next K lines of the output file must contain area parts sorted in non-decreasing order. You answer must be accurate up to 10-4.

Due to floating point precision losses possible, do not consider parts with area not exceeding 10-8.

Sample test(s)

Input
5
0 0 1 0
1 0 1 1
1 1 0 1
0 1 0 0
0 0 1 1

Output
2
0.5000
0.5000

<|response|>
1. Abridged Problem Statement  
Given N infinite lines on the plane (1 ≤ N ≤ 80), they split the plane into regions—some bounded (finite) and some unbounded. Find all finite regions and report their areas in non-decreasing order (precision up to 1e-4), ignoring any region whose area ≤1e-8.

2. Key Observations  
- Any two non‐parallel lines intersect at exactly one point. There are O(N²) intersection points total.  
- These intersections form the vertices of a planar graph; edges are the segments between consecutive intersections along each input line.  
- In a planar straight‐line embedding, each face (region) can be traced by walking around directed edges, always turning “right” (or “left”) at each vertex in angular order.  
- The area of a simple polygon given by its vertex cycle can be computed by the shoelace formula.  

3. Full Solution Approach  

Step A. Read input lines.  
Step B. Compute all pairwise intersections exactly as rational points (to avoid duplicates from floating errors). Store them in a set to deduplicate.  
Step C. Index each unique intersection point from 0…V–1.  
Step D. For each input line:  
  1. Collect all intersection‐points that lie on this line (check collinearity via cross‐product zero).  
  2. Sort these points by their position along the line (parameter t).  
  3. Connect each consecutive pair in this sorted list by an undirected edge.  

Step E. At each vertex u, sort its adjacency list by the angle of the neighbor vector (u→v) in counterclockwise order. This gives a consistent circular order around u.  

Step F. Face Tracing:  
  - Treat each undirected edge {u,v} as two directed edges (u→v) and (v→u).  
  - Maintain a visited set of directed edges.  
  - For each unvisited directed edge (u→v), start a new face-walk:  
      • Mark (u→v) visited, let cycle = [v].  
      • Current directed edge is (u→v). At vertex v, find u’s index in v’s sorted neighbor list; move to the neighbor immediately before that index in cyclic order (i.e., turn “right”). Call it w.  
      • Travel directed edge (v→w), mark visited, append w to cycle, then set (u,v) ← (v,w).  
      • Stop when you return to the starting directed edge.  
  - The collected cycle of vertices forms one face boundary.  

Step G. Compute the signed area of each cycle via the shoelace formula. Keep only areas >1e-8. These correspond to bounded faces if you always turn “right” (you get positively oriented cycles for finite faces).  

Step H. Sort the resulting areas and print the count and each area to 4 decimal places.  

Overall complexity is O(N² log N + E), with E=O(N²), which is fine for N≤80.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

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

struct Rational {
    int64_t n, d;
    Rational(int64_t _n = 0, int64_t _d = 1) : n(_n), d(_d) { normalize(); }

    void normalize() {
        if(d < 0) {
            n = -n;
            d = -d;
        }

        int64_t g = gcd(abs(n), abs(d));
        n /= g;
        d /= g;
    }

    bool operator==(const Rational& o) const { return n == o.n && d == o.d; }
    bool operator<(const Rational& o) const { return n * o.d < o.n * d; }

    Rational operator+(const Rational& o) const {
        return Rational(n * o.d + o.n * d, d * o.d);
    }

    Rational operator-(const Rational& o) const {
        return Rational(n * o.d - o.n * d, d * o.d);
    }

    Rational operator*(const Rational& o) const {
        return Rational(n * o.n, d * o.d);
    }

    Rational operator/(const Rational& o) const {
        return Rational(n * o.d, d * o.n);
    }
};

struct Point {
    Rational x, y;
    Point(Rational _x = 0, Rational _y = 0) : x(_x), y(_y) {}

    bool operator==(const Point& o) const { return x == o.x && y == o.y; }

    bool operator<(const Point& o) const {
        if(!(x == o.x)) {
            return x < o.x;
        }

        return y < o.y;
    }
};

struct Line {
    int64_t x1, y1, x2, y2;
};

int N;
vector<Line> lines;

void read() {
    cin >> N;
    lines.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> lines[i].x1 >> lines[i].y1 >> lines[i].x2 >> lines[i].y2;
    }
}

void solve() {
    // Build the planar arrangement of the N lines and report the areas of all
    // bounded faces, using exact rational coordinates for the vertices.
    //
    // Vertices are all pairwise intersection points (computed exactly as
    // Rational x, y). For each line we collect the vertices lying on it,
    // sort them along the line, and add graph edges between consecutive ones,
    // giving the arrangement graph. To enumerate faces we do a planar face
    // traversal: at every vertex the incident edges are sorted by angle, and
    // walking a directed edge (u, v) we always turn to the previous neighbour
    // (clockwise) around v. Each directed edge belongs to exactly one face, so
    // marking used directed edges enumerates every face once. A face is bounded
    // iff its signed area (shoelace) is positive; we collect those areas,
    // discard ones below 1e-8, and print them sorted.

    set<Point> all_vertices;
    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            int64_t dx1 = lines[i].x2 - lines[i].x1;
            int64_t dy1 = lines[i].y2 - lines[i].y1;
            int64_t dx2 = lines[j].x2 - lines[j].x1;
            int64_t dy2 = lines[j].y2 - lines[j].y1;
            int64_t den = dx1 * dy2 - dy1 * dx2;
            if(den == 0) {
                continue;
            }

            int64_t num_t = (lines[j].x1 - lines[i].x1) * dy2 -
                            (lines[j].y1 - lines[i].y1) * dx2;
            int64_t x_num = lines[i].x1 * den + num_t * dx1;
            int64_t y_num = lines[i].y1 * den + num_t * dy1;
            Point p(Rational(x_num, den), Rational(y_num, den));
            all_vertices.insert(p);
        }
    }

    vector<Point> verts(all_vertices.begin(), all_vertices.end());
    int n = verts.size();
    vector<vector<int>> adj(n);
    map<Point, int> point_to_id;
    for(int i = 0; i < n; i++) {
        point_to_id[verts[i]] = i;
    }

    for(int i = 0; i < N; i++) {
        set<Point> on_line;
        for(int j = 0; j < N; j++) {
            if(i == j) {
                continue;
            }

            int64_t dx1 = lines[i].x2 - lines[i].x1;
            int64_t dy1 = lines[i].y2 - lines[i].y1;
            int64_t dx2 = lines[j].x2 - lines[j].x1;
            int64_t dy2 = lines[j].y2 - lines[j].y1;
            int64_t den = dx1 * dy2 - dy1 * dx2;
            if(den == 0) {
                continue;
            }

            int64_t num_t = (lines[j].x1 - lines[i].x1) * dy2 -
                            (lines[j].y1 - lines[i].y1) * dx2;
            int64_t x_num = lines[i].x1 * den + num_t * dx1;
            int64_t y_num = lines[i].y1 * den + num_t * dy1;
            Point p(Rational(x_num, den), Rational(y_num, den));
            on_line.insert(p);
        }

        vector<Point> pts(on_line.begin(), on_line.end());
        for(size_t k = 0; k + 1 < pts.size(); k++) {
            int a = point_to_id[pts[k]];
            int b = point_to_id[pts[k + 1]];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }

    vector<vector<int>> sorted_neighbors(n);
    for(int i = 0; i < n; i++) {
        vector<int> nb = adj[i];
        sort(nb.begin(), nb.end(), [&](int a, int b) {
            Rational dx1 = verts[a].x - verts[i].x;
            Rational dy1 = verts[a].y - verts[i].y;
            double xx1 = (double)dx1.n / dx1.d;
            double yy1 = (double)dy1.n / dy1.d;
            double ang1 = atan2(yy1, xx1);
            Rational dx2 = verts[b].x - verts[i].x;
            Rational dy2 = verts[b].y - verts[i].y;
            double xx2 = (double)dx2.n / dx2.d;
            double yy2 = (double)dy2.n / dy2.d;
            double ang2 = atan2(yy2, xx2);
            return ang1 < ang2;
        });

        sorted_neighbors[i] = nb;
    }

    set<pair<int, int>> used_directed;
    vector<double> areas;
    for(int i = 0; i < n; i++) {
        for(int j: adj[i]) {
            if(used_directed.count({i, j})) {
                continue;
            }

            vector<int> cycle;
            int curr_u = i;
            int curr_v = j;
            used_directed.insert({curr_u, curr_v});
            cycle.push_back(curr_v);
            while(true) {
                int deg = sorted_neighbors[curr_v].size();
                int k = -1;
                for(int s = 0; s < deg; s++) {
                    if(sorted_neighbors[curr_v][s] == curr_u) {
                        k = s;
                        break;
                    }
                }

                int next_k = (k - 1 + deg) % deg;
                int next_v = sorted_neighbors[curr_v][next_k];
                used_directed.insert({curr_v, next_v});
                curr_u = curr_v;
                curr_v = next_v;
                cycle.push_back(curr_v);
                if(curr_v == j) {
                    break;
                }
            }

            cycle.pop_back();
            int m = cycle.size();
            if(m < 3) {
                continue;
            }

            double signed_area = 0.0;
            for(int kk = 0; kk < m; kk++) {
                int aa = cycle[kk];
                int bb = cycle[(kk + 1) % m];
                double x1 = (double)verts[aa].x.n / verts[aa].x.d;
                double y1 = (double)verts[aa].y.n / verts[aa].y.d;
                double x2 = (double)verts[bb].x.n / verts[bb].x.d;
                double y2 = (double)verts[bb].y.n / verts[bb].y.d;
                signed_area += x1 * y2 - x2 * y1;
            }

            if(signed_area > 1e-8) {
                areas.push_back(signed_area / 2.0);
            }
        }
    }

    sort(areas.begin(), areas.end());
    cout << areas.size() << '\n';
    cout << fixed << setprecision(4);
    for(double ar: areas) {
        cout << ar << '\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();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
from fractions import Fraction
import math

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    lines = []
    for _ in range(N):
        x1 = int(next(it)); y1 = int(next(it))
        x2 = int(next(it)); y2 = int(next(it))
        lines.append((x1,y1,x2,y2))

    # Step B: all intersections as exact Fractions
    pts = set()
    for i in range(N):
        x1,y1,x2,y2 = lines[i]
        dx1, dy1 = x2-x1, y2-y1
        for j in range(i+1, N):
            X1,Y1,X2,Y2 = lines[j]
            dx2, dy2 = X2-X1, Y2-Y1
            det = dx1*dy2 - dy1*dx2
            if det == 0: continue  # parallel
            # solve for parameter t on line i
            num_t = (X1-x1)*dy2 - (Y1-y1)*dx2
            t = Fraction(num_t, det)
            xi = Fraction(x1,1) + t*dx1
            yi = Fraction(y1,1) + t*dy1
            pts.add((xi, yi))

    # index vertices
    verts = list(pts)
    V = len(verts)
    vid = {verts[i]:i for i in range(V)}

    # adjacency
    adj = [[] for _ in range(V)]
    for (x1,y1,x2,y2) in lines:
        dx, dy = x2-x1, y2-y1
        onL = []
        for i,(xi,yi) in enumerate(verts):
            # check collinearity: (xi-x1, yi-y1) cross (dx,dy)==0
            if (xi - x1)*dy == (yi - y1)*dx:
                # compute parameter t
                t = (xi - x1)/dx if dx!=0 else (yi - y1)/dy
                onL.append((t,i))
        onL.sort(key=lambda x: x[0])
        for k in range(1, len(onL)):
            u = onL[k-1][1]
            v = onL[k][1]
            adj[u].append(v)
            adj[v].append(u)

    # sort neighbors by angle
    nbr = [[] for _ in range(V)]
    for i in range(V):
        neigh = sorted(set(adj[i]))
        def ang(j):
            x0 = float(verts[i][0]); y0 = float(verts[i][1])
            x1 = float(verts[j][0]); y1 = float(verts[j][1])
            return math.atan2(y1-y0, x1-x0)
        neigh.sort(key=ang)
        nbr[i] = neigh

    # face tracing
    used = set()
    areas = []
    for u in range(V):
        for v in adj[u]:
            if (u,v) in used: continue
            used.add((u,v))
            cycle = [v]
            pu, pv = u, v
            while True:
                lst = nbr[pv]
                k = lst.index(pu)
                # turn right in cyclic order
                w = lst[(k-1) % len(lst)]
                pu, pv = pv, w
                if (pu,pv) in used: break
                used.add((pu,pv))
                cycle.append(pv)
            if len(cycle) < 3:
                continue
            # compute shoelace area
            A = 0
            M = len(cycle)
            for i in range(M):
                x1,y1 = verts[cycle[i]]
                x2,y2 = verts[cycle[(i+1)%M]]
                A += float(x1*y2 - x2*y1)
            A = 0.5 * abs(A)
            if A > 1e-8:
                areas.append(A)

    areas.sort()
    print(len(areas))
    for a in areas:
        print(f"{a:.4f}")

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