给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
Input输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.
注意:本题的输入数据较多,推荐使用scanf读入数据.
Output对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.
Sample Input
2 5 1 1 4 2 1 3 3 7 2 1.5 5 4.5 3.5 1.25 7.5 4 6 3 10 7 3 0 0 1 1 1 0 2 1 2 0 3 1Sample Output
7.63 0.00
#include<bits/stdc++.h>using namespace std;
#define lson i<<1,l,m
#define rson i<<1|1,m+1,r
const int maxn = 2222;double sum[maxn<<2];
double sum1[maxn<<2];
int cnt[maxn<<2];
double x[maxn];
struct node
{double l,r,h;int d;node(){}node(double l,double r,double h,int d):l(l),r(r),h(h),d(d){}bool operator < (const node& a)const{return h<a.h;}
}ns[maxn];void pushup(int i,int l,int r)
{if(cnt[i]>=2){sum[i] =sum1[i] = x[r+1] - x[l];}else if(cnt[i]==1){sum[i]=sum1[i<<1]+sum1[i<<1|1];sum1[i]=x[r+1]-x[l];}else{sum[i]=sum[i<<1]+sum[i<<1|1];sum1[i]=sum1[i<<1|1]+sum1[i<<1];}
}
void update(int ql,int qr,int v,int i,int l,int r)
{if(ql<=l && qr>=r){cnt[i]+=v;pushup(i,l,r);return;}int m=(l+r)>>1;if(ql<=m)update(ql,qr,v,lson);if(qr>m)update(ql,qr,v,rson);pushup(i,l,r);
}int main()
{int t;cin>>t;while(t--){ memset(cnt,0,sizeof(cnt));//相当于buildmemset(sum,0,sizeof(sum));memset(sum1,0,sizeof(sum1));//相当于buildint n;cin>>n;int m1=0;int m2=0;for(int i=1;i<=n;i++){double x1,x2,y1,y2;scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);x[++m1] = x1;x[++m1] = x2;ns[++m2] = node(x1,x2,y1,1);ns[++m2] = node(x1,x2,y2,-1);}sort(x+1,x+1+m1);sort(ns+1,ns+1+m2);int k;k = unique(x+1,x+1+m1)-x-1;double ans=0;for(int i=1;i<m2;i++){int ql=lower_bound(x+1,x+1+k,ns[i].l)-x;int qr=lower_bound(x+1,x+1+k,ns[i].r)-x;qr--;update(ql,qr,ns[i].d,1,1,k-1);ans+=sum[1]*(ns[i+1].h-ns[i].h);}printf("%.2f\n",ans);}
}