HDU 1255(カバー面積)矩形面積及び

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1255
長方形の面積は同じですが、テーマは二回以上の面積をカバーすることです.そうすると、線分樹に変数を一つ追加して、二回以上の長さをカバーします.更新する時はこの変数に注意してください.
コード:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=2005;
struct line{
    double h,l,r;
    int f;
    line(){}
    line(double a,double b,double c,int d):h(a),l(b),r(c),f(d){}
}lines[maxn];
double xs[maxn];
struct seg{
    double len,dlen;
    int cover;
}sum[maxn<<2];
int linecnt,xcnt;
inline bool cmp(line a,line b){return a.h<b.h;}
inline void addline(double x1,double y1,double x2,double y2){
    xs[++linecnt]=x1;lines[linecnt]=line(y1,x1,x2,1);
    xs[++linecnt]=x2;lines[linecnt]=line(y2,x1,x2,-1);
}
int Search(double k,int l,int r){
    while(l<=r){
        int m=(l+r)>>1;
        if(xs[m]==k)return m;
        if(xs[m]>k)r=m-1;
        else l=m+1;
    }
    return l;
}
inline void pushup(int rt,int l,int r){
    if(sum[rt].cover>=2){
        sum[rt].len=sum[rt].dlen=xs[r+1]-xs[l];
    }
    else if(sum[rt].cover==1){
        sum[rt].len=xs[r+1]-xs[l];
        if(l==r)sum[rt].dlen=0;
        else sum[rt].dlen=sum[rt<<1].len+sum[rt<<1|1].len;
    }
    else{
        if(l==r)sum[rt].len=sum[rt].dlen=0;
        else{
            sum[rt].len=sum[rt<<1].len+sum[rt<<1|1].len;
            sum[rt].dlen=sum[rt<<1].dlen+sum[rt<<1|1].dlen;
        }
    }
}
void update(int L,int R,int c,int l,int r,int rt){
    if(L<=l&&r<=R){
        sum[rt].cover+=c;
        pushup(rt,l,r);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)update(L,R,c,lson);
    if(R>m)update(L,R,c,rson);
    pushup(rt,l,r);
}
int main(){
//    freopen("D://input.txt","r",stdin);
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        linecnt=xcnt=0;
        while(n--){
            double xx[2],yy[2];
            scanf("%lf%lf%lf%lf",&xx[0],&yy[0],&xx[1],&yy[1]);
            addline(xx[0],yy[0],xx[1],yy[1]);
        }
        sort(xs+1,xs+linecnt+1);sort(lines+1,lines+linecnt+1,cmp);
        int i;memset(sum,0,sizeof(sum));
        for(i=1;i<=linecnt;i++){
            if(xs[i+1]!=xs[i])
                xs[++xcnt]=xs[i];
        }
        double area=0;
        for(i=1;i<linecnt;i++){
            int L=Search(lines[i].l,1,xcnt),R=Search(lines[i].r,1,xcnt)-1;
            if(L<=R){
                update(L,R,lines[i].f,1,xcnt,1);
                area+=sum[1].dlen*(lines[i+1].h-lines[i].h);
            }
        }
        printf("%.2f
",area);
    }
    return 0;
}