Problem Description
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
Input
输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.注意:本题的输入数据较多,推荐使用scanf读入数据.
Output
对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.
Sample Input
251 1 4 21 3 3 72 1.5 5 4.53.5 1.25 7.5 46 3 10 730 0 1 11 0 2 12 0 3 1
Sample Output
7.630.00
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<vector>#include<set>#include<map>#define L(x) (x<<1)#define R(x) (x<<1|1)#define MID(x,y) ((x+y)>>1)#define eps 1e-8#define ll long long#define fre(i,a,b) for(i = a; i <b; i++)#define free(i,b,a) for(i = b; i >= a;i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define ssf(n)scanf("%s", n)#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define bugpf("Hi\n")using namespace std;#define INF 0x3f3f3f3f#define N 10005struct stud{ double x1,x2,h; int type; bool operator <(const stud b) const { return h<b.h; }}e[N];struct studd{ int le,ri; int cover; double once,len;}f[N];map<double,int>mp;double x[N];void build(int pos,int le,int ri){f[pos].le=le;f[pos].ri=ri;f[pos].cover=0;f[pos].once=f[pos].len=0;if(le+1==ri) return ;int mid=MID(le,ri);build(L(pos),le,mid);build(R(pos),mid,ri);}void pushup(int pos){if(f[pos].cover>=2){f[pos].len=x[f[pos].ri]-x[f[pos].le];f[pos].once=0;return ;}if(f[pos].cover==1) //这个区间被覆盖一次，，那么两次的应该是下面的两次的加下面的一次的{if(f[pos].le+1==f[pos].ri){f[pos].len=0;f[pos].once=x[f[pos].ri]-x[f[pos].le];}else{f[pos].len=f[L(pos)].len+f[L(pos)].once+f[R(pos)].len+f[R(pos)].once;f[pos].once=x[f[pos].ri]-x[f[pos].le]-f[pos].len;}return ;}if(f[pos].le+1==f[pos].ri){f[pos].len=f[pos].once=0;}else{f[pos].len=f[L(pos)].len+f[R(pos)].len;f[pos].once=f[L(pos)].once+f[R(pos)].once;}}void update(int pos,int le,int ri,int type){if(f[pos].le>=le&&f[pos].ri<=ri){f[pos].cover+=type;pushup(pos);return ;}int mid=MID(f[pos].le,f[pos].ri);if(mid>le)update(L(pos),le,ri,type);if(mid<ri)update(R(pos),le,ri,type);pushup(pos);}int main(){ int i,j,n,k,t; double x1,x2,y1,y2;sf(t); while(t–) {sf(n);k=0;fre(i,0,n){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);if(x1>x2) swap(x1,x2);x[k]=x1;e[k].x1=x1;e[k].x2=x2;e[k].h=y1;e[k++].type=1;x[k]=x2;e[k].x1=x1;e[k].x2=x2;e[k].h=y2;e[k++].type=-1;}sort(x,x+k);sort(e,e+k);n=unique(x,x+k)-x;fre(i,0,n)mp[x[i]]=i;n–;build(1,0,n);double ans=0;fre(i,0,k-1){int le=mp[e[i].x1];int ri=mp[e[i].x2];update(1,le,ri,e[i].type);ans+=f[1].len*(e[i+1].h-e[i].h);}pf("%.2f\n",ans); } return 0;}
海阔凭鱼跃，天高任鸟飞。我要加油，冲向我的理想。
