InputThe input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don’t process it.OutputFor each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.
Sample Input
2 10 10 20 20 15 15 25 25.5 0
Sample Output
Test case #1 Total explored area: 180.00
建立结构体记录每个矩形的情况，用3个double类型变量存储左、右、高。额外用一个变量记录是上底还是下底。由于各个数据都可能是浮点数，需要离散化，离散化时将所有“左”，“右”放入一个数组，
排序去重，再建立一个采用二分法的搜索函数，返回每个值对应的离散化后的数值。用于update的每个l和r的值表示 离散化数组x中 该编号的点到下一个编号的点连线形成的线段。这是因为例如如下的
一条线段
如果按照数组中每个表示一个点来看的话，改变[2,5]时 mid=3 向下进行的update为 [2,3] [4,5]而中间缺少了[3,4]这个区间。但是如果改成离散化数组中每个编号表示一个线段，中间就不会产生
这样的空白。
线段树每个结点表示该结点记录的区间内有多少此刻被标记（即应该算在矩形面积其中的）的线段。扫描线从所有矩形的底边最下面的一条开始进行，每次更新线段树，得到当前的底。这个底一直到下一个
所有矩形中的底出现前，一直都是整个面积中的一部分。即以这个底和 “当前的底与下一个出现的底之间的距离”构成的“若干个矩形”的面积是整体的一部分。将这部分加上，再去看下一个出现边的位置进行
更新。直到进行到最后一条底停止。（这里把每个矩形的上底、下底都叫做底）
1 #include <iostream> 2 //#include<bits/stdc++.h> 3 #include <stack> 4 #include <queue> 5 #include <map> 6 #include <set> 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm> 10 #include <math.h> 11 using namespace std; 12 const int MAX=210; 13 struct node//线段树的结点 14 { 15 int l,r; 16 int mark;//标记情况，为正时计算这部分，非正时不计算（在图中这个高度处此区间为空白） 17 double sum;//区间要计算的线段的长度 18 }st[10*MAX]; 19 struct rectangle 20 { 21 double l,r,h;//矩形的左、右、高 22 int d;//1表示为下边，-1表示为上边 23 rectangle(){} 24 rectangle(double l1,double r1,double h1,int d1):l(l1),r(r1),h(h1),d(d1){}; 25 bool operator < (const rectangle &x)const 26 { 27 return h<x.h; 28 } 29 }seg[MAX]; 30 double hashh[2*MAX];//进行离散化的数组，将每个double值离散化为此数组的下标进行线段树操作 31 void init(int l,int r,int k)//初始化线段树 32 { 33 st[k].l=l; 34 st[k].r=r; 35 st[k].sum=st[k].mark=0; 36 if(l==r) 37 return; 38 init(l,(l+r)/2,2*k); 39 init((l+r)/2+1,r,2*k+1); 40 } 41 void pushup(int k)//更新此k编号的线段树结点 42 { 43 if(st[k].mark) 44 st[k].sum=hashh[st[k].r+1]-hashh[st[k].l]; 45 else if(st[k].r==st[k].l)//未被标记的叶子结点就表示一条线段，不计算在其中，故sum此为0 46 st[k].sum=0; 47 else 48 st[k].sum=st[2*k].sum+st[2*k+1].sum; 49 } 50 void update(int ul,int ur,int l,int r,int k,int d)//更新操作 51 { 52 if(l>=ul&&r<=ur) 53 { 54 st[k].mark+=d; 55 pushup(k); 56 return; 57 } 58 int mid=l+r>>1; 59 if(ul<=mid) 60 update(ul,ur,l,mid,2*k,d); 61 if(ur>mid) 62 update(ul,ur,mid+1,r,2*k+1,d); 63 pushup(k); 64 } 65 int binarysearch(double k,double *x,int n)//二分查找数列中对应k的编号 66 { 67 int l=0,r=n-1; 68 int mid; 69 while(l<=r) 70 { 71 mid=l+r>>1; 72 if(x[mid]==k) 73 return mid; 74 else if(x[mid]<k) 75 l=mid+1; 76 else 77 r=mid-1; 78 } 79 return -1; 80 } 81 int main() 82 { 83 int n,num1,num2; 84 double x1,y1,x2,y2; 85 int ge=0; 86 while(cin>>n,n) 87 { 88 num1=0; 89 num2=1; 90 for(int i=0;i<n;i++)//读入数据 91 { 92 cin>>x1>>y1>>x2>>y2; 93 hashh[num1]=x1; 94 seg[num1++]=rectangle(x1,x2,y1,1); 95 hashh[num1]=x2; 96 seg[num1++]=rectangle(x1,x2,y2,-1); 97 } 98 sort(seg,seg+num1);//排序 99 sort(hashh,hashh+num1); 100 for(int i=1;i<num1;i++)//去重 101 { 102 if(hashh[i]!=hashh[i-1]) 103 hashh[num2++]=hashh[i]; 104 } 105 init(0,num2-1,1);//建立线段树，由于总共0,1,……num2-1为编号的hashh数组有值，树的大小建为 [0,num2-1] 106 int L,R; 107 double ans=0; 108 for(int i=0;i<num1;i++) 109 { 110 L=binarysearch(seg[i].l,hashh,num2); 111 R=binarysearch(seg[i].r,hashh,num2)-1;//由于值表示每个线段的左顶点，故R需要-1 112 update(L,R,0,num2-1,1,seg[i].d); 113 ans+=st[1].sum*(seg[i+1].h-seg[i].h);//st[1].sum就是整个大区间的需要计算的线段长度之和 114 // cout<<ans<<" "; 115 } 116 printf("Test case #%d Total explored area: %.2f ",++ge,ans); 117 } 118 return 0; 119 }