1151:Atlantis

keyword

平面走査法　平面幾何　C++

概要

長方形が複数与えられるのでカバーする面積を求める問題。
Problem 1202 : Mobile Phone Coverageの類題。

int main(){
    int i, j, n, cnt=0;
    double x1, y1, x2, y2;
    while(scanf("%d",&n), n){
        if(cnt++) putchar('\n');
        set<double> eventline;
        vector<double> x1s, y1s, x2s, y2s;
        x1s.reserve(n+1);
        y1s.reserve(n+1);
        x2s.reserve(n+1);
        y2s.reserve(n+1);
        REP(i,n){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            eventline.insert(x1);
            eventline.insert(x2);
            x1s.PB(x1);
            y1s.PB(y1);
            x2s.PB(x2);
            y2s.PB(y2);
        }
        double ans = 0.0, len = 0.0;
        EACH(eventline,it){
            vector< pair<double,double> > ranges;
            ranges.reserve(n+1);
            double lb = -(1<<20);
            REP(i,n){
                if(x1s[i] <= *it && *it < x2s[i])
                    ranges.PB(MP(y1s[i], y2s[i]));
            }
            len = 0;
            sort(ALL(ranges));
            REP(i,SZ(ranges)){
                len += max(0.0,ranges[i].second-max(lb,ranges[i].first));
                lb = max(lb, ranges[i].second);
            }
            if(len > EPS){
                ITER(eventline) itt = it; advance(itt,1);
                ans += len * ((*itt) - (*it));
            }
        }

        printf("Test case #%d\n", cnt);
        printf("Total explored area: %.2f\n", ans);
    }
    return 0;
}