矩形面積及びpoj 1151 Atlanttis

経典のsegtreeのテーマは去年勉強するつもりでしたが、いろいろな原因で遅れました.今年regionalになったら、データ構造を調べて、インターネットの説明を見て、自分で撮りました.直接コードを付けてください.忘れないようにしてください.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define mid (L+R>>1)
#define lson L,mid,P<<1
#define rson mid,R,P<<1|1
const int M = 2010;
class segtree{
public:
    double sum[M<<2],left[M<<2],right[M<<2];
    int num[M<<2];
    double s[M];
    void build(int L,int R,int P){
        left[P]=s[L],right[P]=s[R];
        num[P]=0,sum[P]=0.0;
        if(L+1==R)return ;
        build(lson);
        build(rson);
    }
    void pushup(int x,int L,int R){
        if(num[x]){
            sum[x]=right[x]-left[x];
        }else{
            if(L+1!=R){
                sum[x]=sum[x<<1]+sum[x<<1|1];
            }else{
                sum[x]=0;
            }
        }
    }
    void update(int L,int R,int P,double l,double r,int f){
        if(l==left[P]&&r==right[P]){
            num[P]+=f;
            pushup(P,L,R);
            return ;
        }
        if(l<right[P<<1]){
            update(lson,l,min(right[P<<1],r),f);
        }
        if(r>right[P<<1]){
            update(rson,max(l,right[P<<1]),r,f);
        }
        pushup(P,L,R);
    }
    double query(){return sum[1];}
}tree;
struct Line{
    double x,y1,y2;int f;
    void set(double _x,double _y1,double _y2,int _f){
        x=_x,y1=_y1,y2=_y2,f=_f;
    }
}line[M];
double yy[M];


bool cmp(double a,double b){
    return a<b;
}
bool cmpL(Line a,Line b){
    return a.x<b.x;
}
int main(){
    int n,k,ca=1;
    while(cin>>n,n){
        for(int i=0;i<n;i++){
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[i<<1].set(x1,y1,y2,1);
            line[i<<1|1].set(x2,y1,y2,-1);
            yy[i<<1]=y1,yy[i<<1|1]=y2;
        }
        sort(yy,yy+n*2,cmp);
        sort(line,line+n*2,cmpL);
        k=0;
        for(int i=0;i<n*2;i++){
            if(k==0||tree.s[k]!=yy[i]){
                tree.s[++k]=yy[i];
            }
        }
        tree.build(1,k,1);
        int i,j;double sum=0;
        for(i=0;i<2*n&&line[i].x==line[0].x;i++){
            tree.update(1,k,1,line[i].y1,line[i].y2,line[i].f);
        }
        for(;i<2*n;i=j){
            sum+=tree.query()*(line[i].x-line[i-1].x);
            for(j=i;j<2*n&&line[j].x==line[i].x;j++){
                tree.update(1,k,1,line[j].y1,line[j].y2,line[j].f);
            }
        }
        printf("Test case #%d
",ca++);
        printf("Total explored area: %.2f

",sum);
    }
    return 0;
}