<|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 = \frac{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 (detailed comments)

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

using coord_t = double;
static const coord_t EPS = 1e-9;

// Simple 2D point
struct Point {
    coord_t x, y;
};

// Compute y-value of a non-vertical segment at x using linear interpolation.
// Assumes seg.first.x <= seg.second.x and seg is not vertical.
coord_t y_at(const pair<Point, Point>& seg, coord_t x) {
    const auto& a = seg.first;
    const auto& b = seg.second;
    return a.y + (b.y - a.y) * (x - a.x) / (b.x - a.x);
}

// Check if x lies within segment's x-range (inclusive with EPS).
bool covers_x(const pair<Point, Point>& seg, coord_t x) {
    return x >= seg.first.x - EPS && x <= seg.second.x + EPS;
}

// Check if segment is vertical (projection length is 0).
bool is_vertical(const pair<Point, Point>& seg) {
    return fabs(seg.second.x - seg.first.x) < EPS;
}

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

    int N;
    cin >> N;

    vector<pair<Point, Point>> segs(N);
    vector<char> color(N);

    // Read segments; normalize so that x1 <= x2 (swap endpoints if needed).
    for (int i = 0; i < N; i++) {
        Point p1, p2;
        cin >> p1.x >> p1.y >> p2.x >> p2.y >> color[i];
        if (p1.x > p2.x) swap(p1, p2);
        segs[i] = {p1, p2};
    }

    vector<coord_t> xs;
    xs.reserve(N * N + 2 * N);

    // Add endpoints of non-vertical segments.
    for (int i = 0; i < N; i++) {
        if (is_vertical(segs[i])) continue;
        xs.push_back(segs[i].first.x);
        xs.push_back(segs[i].second.x);
    }

    // Add intersection x-coordinates (within overlap of x-ranges).
    for (int i = 0; i < N; i++) {
        if (is_vertical(segs[i])) continue;

        auto [ai, bi] = segs[i];
        coord_t si = (bi.y - ai.y) / (bi.x - ai.x); // slope
        coord_t ci = ai.y - si * ai.x;             // intercept

        for (int j = i + 1; j < N; j++) {
            if (is_vertical(segs[j])) continue;

            auto [aj, bj] = segs[j];
            coord_t sj = (bj.y - aj.y) / (bj.x - aj.x);
            coord_t cj = aj.y - sj * aj.x;

            // Parallel (or nearly) lines => no unique intersection x.
            if (fabs(si - sj) < 1e-12) continue;

            // Intersection x of supporting lines:
            // si*x + ci = sj*x + cj  => x = (cj - ci) / (si - sj)
            coord_t x = (cj - ci) / (si - sj);

            // Keep only if x is within both segments' x-ranges overlap.
            coord_t lo = max(ai.x, aj.x);
            coord_t hi = min(bi.x, bj.x);
            if (x >= lo - EPS && x <= hi + EPS) xs.push_back(x);
        }
    }

    // Sort and unique with EPS tolerance.
    sort(xs.begin(), xs.end());
    vector<coord_t> ux;
    ux.reserve(xs.size());
    for (coord_t v : xs) {
        if (ux.empty() || fabs(v - ux.back()) >= EPS) ux.push_back(v);
    }
    xs.swap(ux);

    coord_t SR = 0.0, SG = 0.0, SB = 0.0;

    // For each interval, determine the winning segment at the midpoint.
    for (int k = 0; k + 1 < (int)xs.size(); k++) {
        coord_t L = xs[k];
        coord_t R = xs[k + 1];
        coord_t mid = (L + R) / 2.0;
        coord_t len = R - L;

        coord_t best_y = 1e100;
        char best_c = 0;

        for (int i = 0; i < N; i++) {
            if (is_vertical(segs[i])) continue;
            if (!covers_x(segs[i], mid)) continue;

            coord_t y = y_at(segs[i], mid);
            if (y < best_y) {
                best_y = y;
                best_c = color[i];
            }
        }

        // Add interval length to the winning color (if any segment covers it).
        if (best_c == 'R') SR += len;
        else if (best_c == 'G') SG += len;
        else if (best_c == 'B') SB += len;
    }

    cout << fixed << setprecision(2);
    cout << "R " << SR << "\n";
    cout << "G " << SG << "\n";
    cout << "B " << SB << "\n";
    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.