覆盖的面积

/*----------------------------------------------File: F:\ACM源代码\数据结构--线段树\HDU1255.cppDate: 2017/5/30 22:21:39Author: LyuCheng----------------------------------------------*//*题意：给你很多矩形，然后让你求出最少覆盖两次的面积思路：扫描线加一点扩展， 计算面积的时候，忽略覆盖一次的长度，x轴上覆盖超过两次的线段长度*高度    由于我们只需要维护1到max的覆盖长度，所以不需要向下更新，pushup函数，一次维护覆盖过一次的    长度，一次维护覆盖过两次或者以上的长度*/#include<bits/stdc++.h>#define N 2222#define lson i*2,l,m#define rson i*2+1,m+1,rusing namespace std;struct Node{    double l,r,h;    int d;//左右边界，y坐标，是上边界还是下边界    Node (){}    Node(double _l,double _r,double _h,int _d){l=_l;r=_r;h=_h;d=_d;}    bool operator < (const Node &b) const{        return h<b.h;    }};Node node[N*2];//每一个矩形都能产生两条边double X[N*4];//一个矩形有两条边，一条边有两个在x轴上的坐标double sum[N*4];//表示覆盖过的长度double sumd[N*4];//表示覆盖过两次的以上的长度int setd[N*4];void pushupo(int i,int l,int r){//更新覆盖过一次的    if(setd[i]){        sum[i]=X[r+1]-X[l];    }else if(l==r){//如果是叶子结点的话，那么覆盖长度是零        sum[i]=0;    }else{        sum[i]=sum[i*2]+sum[i*2+1];    }}void pushupm(int i,int l,int r){//更新覆盖过两次以上的    if(setd[i]>=2){//覆盖过两次或者以上了        sumd[i]=X[r+1]-X[l];    }else if(l==r){//叶子结点        sumd[i]=0;    }else if(setd[i]==1){        sumd[i]=sum[i*2]+sum[i*2+1];    }else{        sumd[i]=sumd[i*2]+sumd[i*2+1];    }}void update(int ql,int qr,int d,int i,int l,int r){        if(ql<=l&&r<=qr){        setd[i]+=d;        pushupo(i,l,r);        pushupm(i,l,r);        return ;    }        int m=l+(r-l)/2;    if(ql<=m) update(ql,qr,d,lson);    if(m<qr) update(ql,qr,d,rson);    pushupo(i,l,r);    pushupm(i,l,r);}int Seach(double op,int n){//离散化x坐标为整数，这样才能用线段树维护    int l=1,r=n;    while(r>=l){        int m=l+(r-l)/2;        if(X[m]==op)            return m;        else if(X[m]>op)            r=m-1;        else            l=m+1;    }    return -1;}void init(){    memset(sum,0,sizeof sum);    memset(sumd,0,sizeof sumd);    memset(setd,0,sizeof setd);}int main(){        // freopen("in.txt","r",stdin);    int n;    double x1,x2,y1,y2;    int len=0;    int cnt=0;    int t;    scanf("%d",&t);    while(t--){        init();        scanf("%d",&n);        len=0;cnt=0;        for(int i=1;i<=n;i++){            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);            node[++cnt]=Node(x1,x2,y1,1);            node[++cnt]=Node(x1,x2,y2,-1);            X[++len]=x1;            X[++len]=x2;        }        sort(node+1,node+cnt+1);        sort(X+1,X+len+1);        int ans=1;        for(int i=2;i<=len;i++)//进行去重操作            if(X[i]!=X[i-1])                X[++ans]=X[i];        len=ans;        double cur=0;        for(int i=1;i<cnt;i++){            int l=Seach(node[i].l,len);            int r=Seach(node[i].r,len)-1;            if(l<=r)                update(l,r,node[i].d,1,1,len);                    cur+=sumd[1]*(node[i+1].h-node[i].h);        }        printf("%.2lf\n",cur);    }    return 0;}