SGU 192 RGB 6/10

只能用兩個字來形容：『麻煩』
但我越來越喜歡計算幾何搭配其他演算法的題目了

所以要想一個簡單的寫法是很重要的

一開始寫了一個很爛的方法，觀看了他人的作法後發現：

其實我們可以對每一條線段，枚舉每個其他線段遮住該線段的位置

『注意！我原本用的是沒被遮住的，但這樣一個線段就會產生多個線段，不好實現』

因為是遮住，你會發現每一個線段只會產生一條，很容易實現

可是這樣的話就會出現遮住的有重疊的情形，這時先sort，然後用很simple的greedy解決即可

而且找重疊的部份實在很簡單，min, max一下即可

O(n^2lgn)

//By momo
#include
#include
#define N 310
#define EPS 1e-7
using namespace std;

double fabs(double x){ return x<0?-x:x; }
bool same(double a, double b){ return a <= b+EPS && a+EPS >= b; }

struct cord{ double x, y; }S[N];
struct segm{ cord s, e; double m, b; int c; }L[N];
bool comp(cord a, cord b){ return a.x < b.x; }

int n;
void input(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i){
        char s[3];
        scanf("%lf%lf%lf%lf%s", &L[i].s.x, &L[i].s.y, &L[i].e.x, &L[i].e.y, s);
        if(same(L[i].s.x, L[i].e.x)){ --i, --n; continue; }
        L[i].c = (s[0] == 'R'? 0: (s[0] == 'G'? 1: 2));
        if(L[i].s.x > L[i].e.x) swap(L[i].s, L[i].e);
        L[i].m = (L[i].e.y - L[i].s.y) / (L[i].e.x - L[i].s.x);
        L[i].b = L[i].s.y - (L[i].m * L[i].s.x);
    }
}

void solve(){
    static double ans[4];
    for(int i = 0; i < n; i++){
        cord s, e; double sy2, ey2, tot = L[i].e.x-L[i].s.x; int cnt = 0;
        for(int j = 0; j < n; j++) if(i != j){
            s.x = max(L[i].s.x, L[j].s.x), e.x = min(L[i].e.x, L[j].e.x);
            s.y = s.x * L[i].m + L[i].b, sy2 = s.x * L[j].m + L[j].b;
            e.y = e.x * L[i].m + L[i].b, ey2 = e.x * L[j].m + L[j].b;
            if(s.x+EPS >= e.x || same(s.x, e.x)) continue;
            if(sy2+EPS >= s.y && ey2+EPS >= e.y) continue;
            if(s.y+EPS >= sy2 && e.y+EPS >= ey2) S[cnt].x = s.x, S[cnt++].y = e.x;
            else{
                bool v = (s.y+EPS >= sy2);
                double mid = (L[j].b-L[i].b) / (L[i].m-L[j].m);
                S[cnt].x = v?s.x:mid, S[cnt++].y = v?mid:e.x;
            }
        }
        sort(S, S+cnt, comp);
        if(cnt == 0){ ans[L[i].c] += tot; continue; }
        double stt = S[0].x, end = S[0].y;
        for(int j = 1; j < cnt; j++){
            if(end < S[j].x+EPS){
                tot -= end-stt;
                stt = S[j].x;
            }
            end = max(end, S[j].y);
        }ans[L[i].c] += tot-end+stt;
    }
    printf("R %.2lf\nG %.2lf\nB %.2lf\n", ans[0], ans[1], ans[2]);
}

int main(){ input(); solve(); }