覆盖的面积 |
| Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 30 Accepted Submission(s): 23 |
|
Problem Description
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
 |
|
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 1 |
|
Sample Output
7.63 0.00 |
|
Author
Ignatius.L & weigang Lee
|
|
Recommend
Ignatius.L
|
/*---------------------------------------------- File: F:ACM源代码数据结构--线段树HDU1255.cpp Date: 2017/5/30 22:21:39 Author: 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,r using 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 ",cur); } return 0; }