Problem 1202 : Mobile Phone Coverage

keyword

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

概要

100個以下の長方形が与えられる。長方形がカバーする部分の面積を求める問題。
Y軸に平行なイベントラインをずらしていく典型的な平面走査法の問題。区間のカバーする長さを毎回求めてやる。

int main(){
    int i, j, n, cnt=1;
    double r, x, y;
    while(scanf("%d",&n)){
        if(!n) break;
        set<double> eventline;
        vector<double> xs, ys, rs;
        REP(i,n){
            scanf("%lf%lf%lf",&x,&y,&r);
            xs.PB(x);
            eventline.insert(x-r+EPS);
            eventline.insert(x+r+EPS);
            ys.PB(y);
            rs.PB(r);
        }
        double ans = 0.0, len = 0.0;
        EACH(eventline,it){
            vector< pair<double,double> > ranges;
            double lb = -(1<<20);
            REP(i,n){
                if(fabs((*it) - xs[i]) < rs[i])
                    ranges.PB(MP(ys[i] - rs[i], ys[i] + rs[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("%d %.2f\n",cnt++,ans);
    }
    return 0;
}