题目大意：
给你n个矩形，求出它们面积的并。
解题分析：
此题主要用到了扫描线的思想，现将各个矩形的横坐标离散化，然后用它们离散化后的横坐标（相当于将矩形的每条竖线投影在x轴上，然后将它们从0~n-1标号），并且利用这些标好的号建线段树，线段树的每个叶子节点表示离散化后的横坐标(比如从左往右数第一个叶子节点，它的区域表示的就是第0个竖线)。建好数后，就用扫描线从下至上进行扫描，若为下边界，则add[rt]+=1,若为上边界，则add[rt]-=1;扫描线到上面一个边界时，就用高度差*整个区域内的有效长度，即为这一部分矩形的面积。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 #define Lson rt<<1,l,mid 7 #define Rson rt<<1|1,mid+1,r //线段树的每一个节点都有对应的add和sum值 8 const int M =505; 9 int add[M<<2]; //add为区间标记,标记这段区间是否有效(是不是对求面积做出贡献的一段) 10 double sum[M<<2],x[M<<2]; //sum表示这段区间内总共的有效长度 11 12 struct node{ 13 int cnt; //cnt=1为下边，cnt=-1为上边 14 double l,r,h; //分别记录线段的左端，右端和高度 15 node(){} 16 node(double a,double b,double c,int d):l(a),r(b),h(c),cnt(d){} 17 friend bool operator <(node tmp1,node tmp2){ 18 return tmp1.h<tmp2.h; //从下往上扫，所以将h从小到大排序 19 } 20 }s[M<<2]; 21 void Pushup(int rt,int l,int r){ 22 if(add[rt])sum[rt]=x[r+1]-x[l]; //如果这段区域add不为0，则说明这段区域全部有效,由于原来查询的时候是左闭右开，所以这里的真实区域要+1 23 else if(l==r)sum[rt]=0; 24 else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; //求出这段区域的真正有效长度 25 } 26 void update(int rt,int l,int r,int L,int R,int cor){ 27 if(L<=l&&r<=R){ 28 add[rt]+=cor; 29 Pushup(rt,l,r); //由于add标记改变了，所以更新一下tr[rt]的sum值 30 return; 31 } 32 int mid=(l+r)>>1; 33 if(L<=mid)update(Lson,L,R,cor); 34 if(R>mid)update(Rson,L,R,cor); 35 Pushup(rt,l,r); //用递归更新一下路径上的所有sum值 36 } 37 38 int main(){ 39 int n,ncase=0; 40 while(scanf("%d",&n)!=EOF,n){ 41 double a,b,c,d; 42 int m=0; 43 for(int i=0;i<n;i++){ 44 scanf("%lf%lf%lf%lf",&a,&b,&c,&d); 45 x[m]=a; 46 s[m++]=node(a,c,b,1); //矩形下面那条边 47 x[m]=c; 48 s[m++]=node(a,c,d,-1); 49 } 50 sort(x,x+m); 51 sort(s,s+m); 52 memset(add,0,sizeof(add)); //这两个memset相当于建树 53 memset(sum,0,sizeof(sum)); 54 int k=1; 55 for(int i=1;i<m;i++){ 56 if(x[i]!=x[i-1]){ 57 x[k++]=x[i]; //去重 58 } 59 } 60 //0~k-1为离散化后的线段树sum[1]所对应的区域 61 double ans=0; 62 for(int i=0;i<m-1;i++){ //这里只需要循环m-1次就行，因为一共有m-1段面积 63 int l=lower_bound(x,x+k,s[i].l)-x; 64 int r=lower_bound(x,x+k,s[i].r)-x-1; //为避免边的边界重复，我们选取左闭右开区间,所以r要减1 65 update(1,0,k-1,l,r,s[i].cnt); 66 ans+=sum[1]*(s[i+1].h-s[i].h); //sum[1]代表 X(min)~X(max)区域内的有效线段长度，即需要乘以高度差的线段长度 67 } 68 printf("Test case #%d ", ++ncase); 69 printf("Total explored area: %.2lf ", ans); 70 } 71 return 0; 72 }
2018-07-25