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 思路： 同矩形的面积并一样，先自下往上扫面，矩形的下边状态设为1，上边的状态为-1，每次更新线段树的一个区间时都要更新到叶子节点，这样在计算整个区间上的和时只统计状态数大于等于2的叶子节点就好了。代码如下：
#include <stdio.h> #include <algorithm> using namespace std; #define Lroot 2*root+1 #define Rroot 2*root+2 const int MAX_N=5000; struct Line { double l,r,h; int sta; Line(){} Line(double lx,double rx,double hh,int s):l(lx),r(rx),h(hh),sta(s){} bool operator <(Line a){return h<a.h;} }line[2*MAX_N]; struct sT { double sum;int vis; }segTree[3*MAX_N]; double x[2*MAX_N]; int Search(double key,double x[],int m) { int l=-1,r=m,mid; while(l<=r) { mid=(l+r)>>1; if(x[mid]==key)return mid; if(x[mid]>key)r=mid-1; else l=mid+1; } return -1; } void Pushdown(int root,int left,int right) { if(left==right) { if(segTree[root].vis>1)segTree[root].sum=x[right+1]-x[left]; else segTree[root].sum=0; } else if(segTree[root].vis!=0) { segTree[Lroot].vis+=segTree[root].vis; segTree[Rroot].vis+=segTree[root].vis; int mid=(left+right)>>1; Pushdown(Lroot,left,mid);//这里递归的更新子节点，一直更新到叶子结点递归才结束 Pushdown(Rroot,mid+1,right); segTree[root].sum=segTree[Lroot].sum+segTree[Rroot].sum; segTree[root].vis=0; } } void Update(int root,const int &sta,int nleft,int nright,const int &uleft,const int &uright) { int mid=(nleft+nright)>>1; if(nleft>uright||nright<uleft)return; if(nleft>=uleft&&nright<=uright) { segTree[root].vis+=sta; Pushdown(root,nleft,nright); return; } Update(Lroot,sta,nleft,mid,uleft,uright); Update(Rroot,sta,mid+1,nright,uleft,uright); segTree[root].sum=segTree[Lroot].sum+segTree[Rroot].sum; } int main() { //freopen("test.txt","r",stdin); int n;int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<3*MAX_N;i++) { segTree[i].sum=0; segTree[i].vis=0; } double x1,x2,y1,y2;int k=0; for (int i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[k]=Line(x1,x2,y1,1); x[k++]=x1;//离散化x的范围 line[k]=Line(x1,x2,y2,-1); x[k++]=x2; } sort(x,x+k); sort(line,line+k); int m=0; x[m++]=x[0]; for(int i=0;i<k-1;i++)//去重 if(x[i]!=x[i+1])x[m++]=x[i+1]; double ans=0; for (int i=0;i<k;i++) { int L=Search(line[i].l,x,m); int R=Search(line[i].r,x,m)-1; Update(0,line[i].sta,0,m-1,L,R); ans+=segTree[0].sum*(line[i+1].h-line[i].h); } printf("%.2lf\n",ans); } }