【HDU】1542 Atlantis

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cmath>
  5 #define EPS 1e-9
  6 #define MAXN 210
  7 struct Line
  8 {
  9     double left,right,high;
 10     int flag;
 11 };
 12 struct node
 13 {
 14     int cover;
 15     double len;
 16 };
 17 node tree[MAXN<<2];
 18 Line p[MAXN];
 19 double x[MAXN];
 20 int cmp1(const void *a,const void *b)
 21 {
 22     return (*(Line *)a).high>(*(Line *)b).high?1:-1;
 23 }
 24 int cmp2(const void *a,const void *b)
 25 {
 26     return *(double *)a>*(double *)b?1:-1;
 27 }
 28 bool Equal(double x,double y)
 29 {
 30     return fabs(x-y)<EPS;
 31 }
 32 void Build(int L,int R,int rt)
 33 {
 34     tree[rt].cover=0;
 35     tree[rt].len=0;
 36     if(L!=R)
 37     {
 38         int mid=(L+R)>>1;
 39         Build(L,mid,rt<<1);
 40         Build(mid+1,R,rt<<1|1);
 41     }
 42 }
 43 int Bin(double val,int low,int high)
 44 {
 45     int mid;
 46     while(low<high)
 47     {
 48         mid=(low+high)>>1;
 49         if(Equal(val,x[mid]))
 50             return mid;
 51         if(val>x[mid])
 52             low=mid+1;
 53         else
 54             high=mid;
 55     }
 56 }
 57 inline void PushUp(int L,int R,int rt)
 58 {
 59     if(tree[rt].cover)
 60         tree[rt].len=x[R+1]-x[L];
 61     else if(L==R)
 62         tree[rt].len=0;
 63     else
 64         tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len;
 65 }
 66 void Update(int st,int en,int flag,int L,int R,int rt)
 67 {
 68     if(st<=L&&R<=en)
 69     {
 70         tree[rt].cover+=flag;
 71         PushUp(L,R,rt);
 72     }
 73     else
 74     {
 75         int mid=(L+R)>>1;
 76         if(mid>=st)
 77             Update(st,en,flag,L,mid,rt<<1);
 78         if(en>mid)
 79             Update(st,en,flag,mid+1,R,rt<<1|1);
 80         PushUp(L,R,rt);
 81     }
 82 }
 83 int main()
 84 {
 85     double x1,y1,x2,y2,ans;
 86     int n,m,i,k,u,v,ca=1;
 87     while(scanf("%d",&n),n)
 88     {
 89         for(i=k=0;i<n;i++)
 90         {
 91             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
 92             x[k]=x1;
 93             p[k].flag=-1;
 94             p[k].left=x1;
 95             p[k].right=x2;
 96             p[k++].high=y2;
 97             x[k]=x2;
 98             p[k].flag=1;
 99             p[k].left=x1;
100             p[k].right=x2;
101             p[k++].high=y1;
102         }
103         qsort(p,k,sizeof(p[0]),cmp1);
104         qsort(x,k,sizeof(x[0]),cmp2);
105         for(m=i=0;i<k;i++)
106         {
107             if(!Equal(x[m],x[i]))
108                 x[++m]=x[i];
109         }
110         Build(0,m-1,1);
111         for(ans=i=0;i<k-1;i++)
112         {
113             u=Bin(p[i].left,0,m+1);
114             v=Bin(p[i].right,0,m+1);
115             Update(u,v-1,p[i].flag,0,m-1,1);
116             ans+=(p[i+1].high-p[i].high)*tree[1].len;
117         }
118         printf("Test case #%d\nTotal explored area: %.2lf\n\n",ca++,ans);
119     }
120     return 0;
121 }
新博客：www.zhixiangli.com