Problem Description

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

 

Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.

注意:本题的输入数据较多,推荐使用scanf读入数据.

 

Output

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.

 

Sample Input

 

Sample Output

 

Author

Ignatius.L & weigang Lee

 

//cnt[rt]>=2的一定是覆盖过两次以上的，直接计算。cnt[rt]==1时，如果rt的左右儿子

//被覆盖过大于等于1次，那么再被他们父亲覆盖上就是覆盖过两次了，值是左右儿子被

//覆盖过一次的长度的和。cnt[rt]==0照常更新。sum2记录覆盖过两次以上的边的长度。

//sum1记录覆盖过一次的边的长度。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

double sum1[maxn*],sum2[maxn*],mp[maxn];

int cnt[maxn*];

struct node{

    double l,r,h;

    int d;

    node(){}

    node(double a,double b,double c,int d):l(a),r(b),h(c),d(d){}

    bool operator < (const node &p)const{

        if(h==p.h) return d>p.d;

        return h<p.h;

    }

}nodes[maxn*];

int Bsearch(double a,int b,double *c)

{

    int l=,r=b-,mid;

    while(l<=r){

        mid=(l+r)>>;

        if(c[mid]==a) return mid;

        else if(c[mid]>a) r=mid-;

        else l=mid+;

    }

    return -;

}

void Pushup(int l,int r,int rt)

{

    if(cnt[rt]){

        sum1[rt]=mp[r+]-mp[l];

        if(cnt[rt]==)

            sum2[rt]=sum1[rt<<]+sum1[rt<<|];

        else sum2[rt]=mp[r+]-mp[l];

    }

    else if(l==r) sum1[rt]=sum2[rt]=;

    else{

        sum1[rt]=sum1[rt<<]+sum1[rt<<|];

        sum2[rt]=sum2[rt<<]+sum2[rt<<|];

    }

}

void Update(int ql,int qr,int v,int l,int r,int rt)

{

    if(ql<=l&&qr>=r){

        cnt[rt]+=v;

        Pushup(l,r,rt);

        return;

    }

    //if(l==r) return;

    int m=(l+r)>>;

    if(ql<=m) Update(ql,qr,v,l,m,rt<<);

    if(qr>m) Update(ql,qr,v,m+,r,rt<<|);

    Pushup(l,r,rt);

}

int main()

{

    int t,n;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        int m=,nu=;

        double x1,y1,x2,y2;

        memset(sum1,,sizeof(sum1));

        memset(sum2,,sizeof(sum2));

        memset(cnt,,sizeof(cnt));

        for(int i=;i<n;i++){

            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);

            nodes[m++]=node(x1,x2,y1,);

            nodes[m++]=node(x1,x2,y2,-);

            mp[nu++]=x1;mp[nu++]=x2;

        }

        sort(mp,mp+nu);

        nu=unique(mp,mp+nu)-mp;

        sort(nodes,nodes+m);

        double ans=;

        for(int i=;i<m-;i++){

            int lef=Bsearch(nodes[i].l,nu,mp);

            int rig=Bsearch(nodes[i].r,nu,mp)-;

            if(lef<=rig)

                Update(lef,rig,nodes[i].d,,nu-,);

            ans+=sum2[]*(nodes[i+].h-nodes[i].h);

        }

        printf("%.2lf\n",ans);

    }

    return ;

}