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

192. RGB
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



There are N segments on a plane (0<N<=300). Each segment is defined by coordinates of the end points (Xi1, Yi1) and (Xi2, Yi2) (i=1,2,...,N). All coordinates are in a range from 0 to 32000. No two segments have more than one common point. Each segment is painted in one of three colors: red (R), green (G), blue (B). All points of all segments are projected to the axis OX (projection is made parallel to the axis OY). Each projected point is painted in color of the point nearest to the axis OX. You have to find the total lengths of the projections painted in red (SR), green (SG) and blue (SB) colors.

Input
The first line contains natural number N. Each of the following N lines contains coordinates of the ends of the segments (4 integer delimited by a space) and the letter (R, G, B), determining the color of a segment.

Output
The first line must contain letter R and number SR delimited by a space. The second line must contain letter G and number SG. The third line must contain letter B and number SB. All numbers should be printed with precision 0.01.

Sample test(s)

Input
4
1 1 3 2 R
2 1 4 2 G
3 1 5 2 B
2 2 3 5 R

Output
R 1
G 1
B 2
Author:	German G. Narkaytis
Resource:	ACM International Collegiate Programming Contest 2003-2004
North-Eastern European Region, Southern Subregion
Date:	2003 October, 9

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

Given up to **N = 300** colored line segments (color ∈ {R, G, B}) on the plane. Project all their points vertically onto the **x-axis**.
For each \(x\) on the axis, look at all segment points with that \(x\); the projection at \(x\) gets the color of the point **closest to the x-axis** (i.e., with minimal \(y\)).
Compute total x-axis length colored **R**, **G**, and **B**, and print each with precision **0.01**.

Constraint: no two segments share more than one common point.

---

## 2) Key observations needed to solve the problem

1. **Each non-vertical segment defines a linear function \(y(x)\)** on its x-interval \([x_{\min}, x_{\max}]\).
   For a fixed \(x\), the visible (closest-to-axis) color is the segment with **minimum \(y(x)\)** among those covering \(x\).

2. The identity of the segment with minimum \(y(x)\) can only change at **critical x-coordinates**:
   - **segment endpoints** (a segment starts/ends covering x),
   - **intersection x-coordinates** of two segments' supporting lines (where their order by y can swap), but only if that intersection lies within the overlap of their x-ranges.

3. Therefore, between any two consecutive critical x-values, the "winner" segment (minimum y) is constant.
   So we can pick a **midpoint** in each interval, determine the winner at that midpoint, and add the interval length to that winner's color sum.

4. **Vertical segments** (\(x_1 = x_2\)) project to a single point on x-axis ⇒ **zero length** contribution. They can be ignored for length sums.

---

## 3) Full solution approach

### Step A: Read and normalize segments
For each segment, store endpoints as doubles (for intersection math), and reorder endpoints so that \(x_1 \le x_2\). Also store its color.

### Step B: Build the set of critical x-values
Create array `xs`:

1. For every **non-vertical** segment, add both x-endpoints.
2. For every pair of **non-vertical** segments \(i, j\):
   - Write each supporting line as \(y = s x + c\).
   - If slopes are equal (parallel), skip.
   - Compute intersection x: \(x = (c_j - c_i) / (s_i - s_j)\).
   - Keep this \(x\) only if it lies within the **overlap** of the two segments' x-ranges: \(x \in [\max(x_{i1}, x_{j1}), \min(x_{i2}, x_{j2})]\).
   - Add it to `xs`.

Sort `xs` and remove near-duplicates with epsilon.

### Step C: Sweep intervals between consecutive critical x-values
For each consecutive pair \([xs[k], xs[k+1]]\):

- Let `mid = (xs[k] + xs[k+1]) / 2`.
- Among all non-vertical segments whose x-range contains `mid`, compute \(y(\text{mid})\) by linear interpolation: \(y = y_1 + (y_2 - y_1)\frac{mid - x_1}{x_2 - x_1}\).
- Pick the segment with smallest y. Its color owns the whole interval.
- Add interval length `xs[k+1] - xs[k]` to that color's total.

If no segment covers `mid`, the interval contributes nothing.

### Complexity
- Critical x-values: \(O(N^2)\) (endpoints + pair intersections)
- Intervals: \(O(N^2)\)
- For each interval scan all segments: \(O(N)\)

Total worst-case: **\(O(N^3)\)**, with \(N \le 300\) acceptable in practice for this problem.

---

## 4) C++ implementation

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

int n;
vector<pair<Point, Point>> segments;
vector<char> colors;

coord_t y_at(const pair<Point, Point>& seg, coord_t x) {
    auto& [a, b] = seg;
    return a.y + (b.y - a.y) * (x - a.x) / (b.x - a.x);
}

bool covers(const pair<Point, Point>& seg, coord_t x) {
    return x >= seg.first.x - 1e-9 && x <= seg.second.x + 1e-9;
}

void read() {
    cin >> n;
    segments.resize(n);
    colors.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> segments[i].first >> segments[i].second >> colors[i];
        if(segments[i].first.x > segments[i].second.x) {
            swap(segments[i].first, segments[i].second);
        }
    }
}

void solve() {
    // We can first notice that when we project there are at most O(n^2)
    // "maximal" ranges that have the same colour, defined by the X-s of all
    // intersection points and borders of the original segments. So we will
    // start by finding all relevant X values and sorting them. Then in each
    // interval, we want to find the closest line segment and this would be the
    // colour we want. Note that because we consider all intersections, for any
    // point of the segment, the closest segment would be the same. Therefore,
    // an easy approach is that for each of these O(n^2) points we will consider
    // the midpoints m, and then evaluate all segments that "cover" the
    // corresponding range and choose the smallest f(m), where f(m) is the
    // linear function defined by the segment. This can be done with a simple
    // O(n) loop giving us a O(n^3) solution.
    //
    // The O(n^3) solution is enough to pass and this is what we implement, but
    // there is also a way to speed it up to at least O(n^2 log n). We can use
    // a Li Chao or dynamic convex hull. Each line acts as a linear function for
    // a range of X values and we can build a segment tree over the ranges we
    // are interested in, such that each of the n segment splits into at most
    // O(log n) of them. We then do a walk on the tree, and query the state in
    // the leafs. The part we should be careful about is the fact that we need
    // to "undo" the updates, so a persistent Li Chao is a good option. There
    // are at most O(n log n) updates, each in O(log n), and there are O(n^2)
    // leafs which we have to query. This yields a direct O(n^2 log n) bound.

    vector<coord_t> xs;
    for(auto& [a, b]: segments) {
        if(abs(b.x - a.x) < 1e-9) {
            continue;
        }
        xs.push_back(a.x);
        xs.push_back(b.x);
    }

    for(int i = 0; i < n; i++) {
        auto& [ai, bi] = segments[i];
        if(abs(bi.x - ai.x) < 1e-9) {
            continue;
        }
        coord_t si = (bi.y - ai.y) / (bi.x - ai.x);
        coord_t ci = ai.y - si * ai.x;
        for(int j = i + 1; j < n; j++) {
            auto& [aj, bj] = segments[j];
            if(abs(bj.x - aj.x) < 1e-9) {
                continue;
            }
            coord_t sj = (bj.y - aj.y) / (bj.x - aj.x);
            coord_t cj = aj.y - sj * aj.x;
            if(abs(si - sj) < 1e-12) {
                continue;
            }
            coord_t x = (cj - ci) / (si - sj);
            coord_t lo = max(ai.x, aj.x);
            coord_t hi = min(bi.x, bj.x);
            if(x >= lo - 1e-9 && x <= hi + 1e-9) {
                xs.push_back(x);
            }
        }
    }

    sort(xs.begin(), xs.end());
    xs.erase(
        unique(
            xs.begin(), xs.end(),
            [](coord_t a, coord_t b) { return abs(a - b) < 1e-9; }
        ),
        xs.end()
    );

    coord_t sr = 0, sg = 0, sb = 0;

    for(int i = 0; i + 1 < (int)xs.size(); i++) {
        coord_t mid = (xs[i] + xs[i + 1]) / 2.0;
        coord_t len = xs[i + 1] - xs[i];
        coord_t best_y = 1e18;
        char best_color = '?';
        for(int j = 0; j < n; j++) {
            if(abs(segments[j].second.x - segments[j].first.x) < 1e-9) {
                continue;
            }
            if(!covers(segments[j], mid)) {
                continue;
            }
            coord_t y = y_at(segments[j], mid);
            if(y < best_y) {
                best_y = y;
                best_color = colors[j];
            }
        }
        if(best_color == 'R') {
            sr += len;
        } else if(best_color == 'G') {
            sg += len;
        } else if(best_color == 'B') {
            sb += len;
        }
    }

    cout << fixed << setprecision(2);
    cout << "R " << sr << "\n";
    cout << "G " << sg << "\n";
    cout << "B " << sb << "\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 implementation (detailed comments)

```python
import sys
import math

EPS = 1e-9

def is_vertical(seg):
    (x1, y1), (x2, y2) = seg
    return abs(x2 - x1) < EPS

def covers_x(seg, x):
    (x1, _), (x2, _) = seg
    return x >= x1 - EPS and x <= x2 + EPS

def y_at(seg, x):
    """Compute y on a non-vertical segment at coordinate x."""
    (x1, y1), (x2, y2) = seg
    return y1 + (y2 - y1) * (x - x1) / (x2 - x1)

def unique_sorted(xs):
    xs.sort()
    res = []
    for v in xs:
        if not res or abs(v - res[-1]) >= EPS:
            res.append(v)
    return res

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

    segs = []
    colors = []

    # Read and normalize segments so x1 <= x2
    for _ in range(n):
        x1 = float(next(it)); y1 = float(next(it))
        x2 = float(next(it)); y2 = float(next(it))
        c = next(it)
        if x1 > x2:
            x1, x2 = x2, x1
            y1, y2 = y2, y1
        segs.append(((x1, y1), (x2, y2)))
        colors.append(c)

    xs = []

    # Add endpoints of non-vertical segments
    for seg in segs:
        if is_vertical(seg):
            continue
        (x1, _), (x2, _) = seg
        xs.append(x1)
        xs.append(x2)

    # Add x-coordinates of supporting-line intersections (inside overlapping x-ranges)
    for i in range(n):
        if is_vertical(segs[i]):
            continue
        (xi1, yi1), (xi2, yi2) = segs[i]
        si = (yi2 - yi1) / (xi2 - xi1)
        ci = yi1 - si * xi1

        for j in range(i + 1, n):
            if is_vertical(segs[j]):
                continue
            (xj1, yj1), (xj2, yj2) = segs[j]
            sj = (yj2 - yj1) / (xj2 - xj1)
            cj = yj1 - sj * xj1

            # Parallel lines => no unique intersection x
            if abs(si - sj) < 1e-12:
                continue

            x = (cj - ci) / (si - sj)

            lo = max(xi1, xj1)
            hi = min(xi2, xj2)
            if x >= lo - EPS and x <= hi + EPS:
                xs.append(x)

    xs = unique_sorted(xs)

    sr = sg = sb = 0.0

    # Evaluate each interval by midpoint
    for k in range(len(xs) - 1):
        L = xs[k]
        R = xs[k + 1]
        mid = (L + R) / 2.0
        length = R - L

        best_y = 1e100
        best_c = None

        for seg, c in zip(segs, colors):
            if is_vertical(seg):
                continue
            if not covers_x(seg, mid):
                continue
            y = y_at(seg, mid)
            if y < best_y:
                best_y = y
                best_c = c

        if best_c == 'R':
            sr += length
        elif best_c == 'G':
            sg += length
        elif best_c == 'B':
            sb += length
        # else: no segment covers this interval => contributes nothing

    print(f"R {sr:.2f}")
    print(f"G {sg:.2f}")
    print(f"B {sb:.2f}")

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

This directly implements the "critical x-values + midpoint winner" method described above and matches the required output format/precision.
