描述
在2051年，若干火星探险队探索了这颗红色行星的不同的区域并且制作了这些区域的地图。现在, Baltic空间机构有一个雄心勃勃的计划：他们想制作一张整个行星的地图。为了考虑必要的工作，他们需要知道地图上已经存在的全部区域的大小。你的任务是写一个计算这个区域大小的程序。
任务：
l 从输入读取地图形状的描述
2 计算地图覆盖的全部的区域
3 输出
输入
输入第一行包含一个整数N(1<=N<=10000)，表示可得到的地图数目。
以下N行，每行描述一张地图。
每行包含4个整数x1，y1，x2和y2(0<=x1<x2<=30000，0<=y1<y2<=30 000)。数值(x1，y1)和(x2，y2)是坐标，分别表示绘制区域的左上角和右下角坐标。每张地图是矩形的，并且它的边是平行与X坐标轴或Y坐标轴的。
输出
输出应该包含一个整数，表示探索区域的总面积(即所有矩形的公共面积)。
样例输入
2
10 10 20 20
15 15 25 30
样例输出
225
1 #include <iostream> 2 #include <algorithm> 3 #include <stdio.h> 4 using namespace std; 5 const int maxsize = 80010; 6 7 struct node 8 { 9 int st,ed,c; 10 int m;//c为区间被覆盖的层数，m为区间的测度 11 } ST[maxsize]; 12 struct line 13 { 14 int x,y1,y2; 15 bool s; //s=1表示直线为矩形的左边，s=0，表示直线为矩形的右边 16 } Line[maxsize]; 17 18 int y[maxsize],ty[maxsize]; 19 //y[]为矩形与浮点数的对应数组，ty[]为用来求y[]的辅助数组 20 21 void build (int root,int st,int ed) 22 { 23 ST[root].st = st; 24 ST[root].ed = ed; 25 ST[root].c = 0; 26 ST[root].m = 0; 27 if(ed-st>1) 28 { 29 int mid = (st+ed)/2; 30 build(root<<1,st,mid); 31 build(root<<1|1,mid,ed); 32 } 33 } 34 35 inline void update(int root) 36 { 37 if(ST[root].c>0) ST[root].m = y[ST[root].ed-1] - y[ST[root].st-1]; 38 else if(ST[root].ed-ST[root].st==1) ST[root].m=0; 39 else ST[root].m = ST[root<<1].m+ST[root<<1|1].m; 40 } 41 void insert(int root,int st,int ed) 42 { 43 if(st<=ST[root].st && ST[root].ed<=ed) 44 { 45 ST[root].c++; 46 update(root); 47 return ; 48 } 49 int mid = (ST[root].ed + ST[root].st)/2; 50 if(st < mid) insert(root<<1,st,ed); 51 if(ed > mid) insert(root<<1|1,st,ed); 52 update(root); 53 } 54 55 void Delete(int root,int st,int ed) 56 { 57 if(st <= ST[root].st && ST[root].ed<=ed) 58 { 59 ST[root].c--; 60 update(root); 61 return ; 62 } 63 int mid = (ST[root].st + ST[root].ed)/2; 64 if(st<mid) Delete(root*2,st,ed); 65 if(ed>mid) Delete(root*2+1,st,ed); 66 update(root); 67 } 68 int indexs[30010]; 69 bool cmp(line l1,line l2) 70 { 71 return l1.x<l2.x; 72 } 73 74 int main() 75 { 76 int n,num; 77 while(~scanf("%d",&n)) 78 { 79 for(int i=0; i<n; i++) 80 { 81 int x1,x2,y1,y2; 82 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 83 Line[2*i].x=x1,Line[2*i].y1=y1; 84 Line[2*i].y2=y2,Line[2*i].s=1; 85 Line[2*i+1].x=x2,Line[2*i+1].y1=y1; 86 Line[2*i+1].y2=y2,Line[2*i+1].s=0; 87 88 ty[2*i]=y1; 89 ty[2*i+1]=y2; 90 } 91 n<<=1; 92 sort(Line,Line+n,cmp); 93 sort(ty,ty+n); 94 y[0] = ty[0]; 95 //处理数组ty[]使之不含有、重复元素，得到新的数组存放到数组y[]中 96 for(int i=num=1; i<n; i++) 97 if(ty[i]!=ty[i-1]) 98 y[num++] = ty[i]; 99 for(int i=0; i<num; i++) indexs[y[i]] = i; 100 build(1,1,num); 101 long long area =0; 102 for(int i=0; i<n-1; i++) 103 { 104 int l = indexs[Line[i].y1]+1,r = indexs[Line[i].y2]+1; 105 if(Line[i].s) insert(1,l,r); //插入矩形的左边 106 else Delete(1,l,r); //删除矩形的右边 107 area += (long long) ST[1].m * (long long)(Line[i+1].x - Line[i].x); 108 } 109 110 printf("%I64d\n",area); 111 } 112 113 return 0; 114 }