hdu 1542 Atlantis

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #define INF 99999999
11 using namespace std;
12 
13 const int MAX=200+10;
14 int mark[MAX<<2];//记录某个区间的下底边个数
15 double sum[MAX<<2];//记录某个区间的下底边总长度
16 double lisan[MAX];//对x进行离散化,否则x为浮点数且很大无法进行线段树
17 
18 //以横坐标作为线段(区间),对横坐标线段进行扫描
19 //扫描的作用是每次更新下底边总长度和下底边个数,增加新面积
20 struct seg{//线段
21     double l,r,h;
22     int d;
23     seg(){}
24     seg(double x1,double x2,double H,int c):l(x1),r(x2),h(H),d(c){}
25     bool operator<(const seg &a)const{
26         return h<a.h;
27     }
28 }s[MAX];
29 
30 void Upfather(int n,int left,int right){
31     if(mark[n])sum[n]=lisan[right+1]-lisan[left];//表示该区间整个线段长度可以作为底边
32     else if(left == right)sum[n]=0;//叶子结点则底边长度为0(区间内线段长度为0)
33     else sum[n]=sum[n<<1]+sum[n<<1|1];
34 }
35 
36 void Update(int L,int R,int d,int n,int left,int right){
37     if(L<=left && right<=R){//该区间是当前扫描线段的一部分,则该区间下底边总长以及上下底边个数差更新
38         mark[n]+=d;//更新底边相差差个数
39         Upfather(n,left,right);//更新底边长
40         return;
41     }
42     int mid=left+right>>1;
43     if(L<=mid)Update(L,R,d,n<<1,left,mid);
44     if(R>mid)Update(L,R,d,n<<1|1,mid+1,right);
45     Upfather(n,left,right);
46 }
47 
48 int search(double key,double* x,int n){
49     int left=0,right=n-1;
50     while(left<=right){
51         int mid=left+right>>1;
52         if(x[mid] == key)return mid;
53         if(x[mid]>key)right=mid-1;
54         else left=mid+1;
55     }
56     return -1;
57 }
58 
59 int main(){
60     int n,num=0;
61     double x1,x2,y1,y2;
62     while(cin>>n,n){
63         int k=0;
64         for(int i=0;i<n;++i){
65             cin>>x1>>y1>>x2>>y2;
66             lisan[k]=x1;
67             s[k++]=seg(x1,x2,y1,1);
68             lisan[k]=x2;
69             s[k++]=seg(x1,x2,y2,-1);
70         }
71         sort(lisan,lisan+k);
72         sort(s,s+k);
73         int m=1;
74         for(int i=1;i<k;++i)//去重复端点
75             if(lisan[i] != lisan[i-1])lisan[m++]=lisan[i];
76         double ans=0;
77         //memset(mark,0,sizeof mark);
78         //memset(sum,0,sizeof sum);//如果下面是i<k-1,则要初始化,因为如果对第k-1条,线段扫描时会使得mark,sum为0才不用初始化的
79         for(int i=0;i<k;++i){//扫描线段
80             int L=search(s[i].l,lisan,m);
81             int R=search(s[i].r,lisan,m)-1;
82             Update(L,R,s[i].d,1,0,m-1);//扫描线段时更新底边长度和底边相差个数
83             ans+=sum[1]*(s[i+1].h-s[i].h);//新增加面积
84         }
85         printf("Test case #%d\nTotal explored area: %.2lf\n\n",++num,ans);
86     }
87     return 0;
88 }