hdu 1542 Atlantis

题意：给出n个矩形的左下坐标和右上坐标，求出总面积。

在写pushup函数时，没有考虑l==r的情况，wa了很久。看了其他大牛的解题报告才想起来的。╭(╯^╰)╮

View Code

  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 #define lson l,m,rt<<1
  5 #define rson m+1,r,rt<<1|1
  6 #define maxn 205
  7 struct node
  8 {
  9     double len;
 10     int cnt;
 11 }setree[maxn<<2];
 12 double xx[maxn<<1];
 13 struct 
 14 {
 15     double l,r,high;
 16     int side;
 17 }mes[maxn<<1];
 18 void quicksort(int l,int r)
 19 {
 20     if(l>=r)
 21     return;
 22     int i=l,j=r;
 23     double tl=mes[l].l,tr=mes[l].r,tside=mes[l].side,thigh=mes[l].high;
 24     while(i<j){
 25         while(mes[j].high>=thigh&&i<j)
 26         j--;
 27         if(i<j){
 28             mes[i].l=mes[j].l;
 29             mes[i].r=mes[j].r;
 30             mes[i].side=mes[j].side;
 31             mes[i].high=mes[j].high;
 32             i++;
 33         }
 34         while(mes[i].high<thigh&&i<j)
 35         i++;
 36         if(i<j){
 37             mes[j].l=mes[i].l;
 38             mes[j].r=mes[i].r;
 39             mes[j].side=mes[i].side;
 40             mes[j].high=mes[i].high;
 41             j--;
 42         }
 43     }
 44     mes[i].l=tl;
 45     mes[i].r=tr;
 46     mes[i].side=tside;
 47     mes[i].high=thigh;
 48     quicksort(l,i-1);
 49     quicksort(i+1,r);
 50 }
 51 int binsearch(int l,int r,double key)
 52 {
 53     int m=(l+r)>>1;
 54     if(xx[m]==key)
 55     return m;
 56     if(xx[m]>key)
 57     return binsearch(l,m-1,key);
 58     return binsearch(m+1,r,key);
 59 }
 60 void pushup(int rt,int l,int r)
 61 {
 62     if(setree[rt].cnt)
 63     setree[rt].len=xx[r+1]-xx[l];
 64     else if(l==r)
 65     setree[rt].len=0;
 66     else
 67     setree[rt].len=setree[rt<<1].len+setree[rt<<1|1].len;
 68 }
 69 void build(int l,int r,int rt)
 70 {
 71     setree[rt].cnt=0;
 72     setree[rt].len=0;
 73     if(l==r)
 74     return;
 75     int m=(l+r)>>1;
 76     build(lson);
 77     build(rson);
 78 }
 79 void update(int l,int r,int rt,int L,int R,int cnt)
 80 {
 81     if(L<=l&&r<=R){
 82         setree[rt].cnt+=cnt;
 83         pushup(rt,l,r);
 84         return;
 85     }
 86     int m=(l+r)>>1;
 87     if(L<=m)
 88     update(lson,L,R,cnt);
 89     if(R>m)
 90     update(rson,L,R,cnt);
 91     pushup(rt,l,r);
 92 }
 93 int main()
 94 {
 95     int n,k,i,cas=1;
 96     while(scanf("%d",&n)&&n){
 97         double a,b,c,d;
 98         int m=0,k;
 99         for(i=0;i<n;i++){
100             scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
101             mes[m].l=mes[m+1].l=xx[m]=a;
102             mes[m].r=mes[m+1].r=xx[m+1]=c;
103             mes[m].high=b;
104             mes[m].side=1;
105             mes[m+1].high=d;
106             mes[m+1].side=-1;
107             m+=2;
108         }
109         sort(xx,xx+m);
110         for(k=1,i=1;i<m;i++)
111         if(xx[i]!=xx[i-1])
112         xx[k++]=xx[i];
113         quicksort(0,m-1);
114         double ret=0;
115         build(0,k-1,1);
116         for(i=0;i<m-1;i++){
117             int l=binsearch(0,k-1,mes[i].l);
118             int r=binsearch(0,k-1,mes[i].r)-1;
119             update(0,k-1,1,l,r,mes[i].side);
120             ret+=(mes[i+1].high-mes[i].high)*setree[1].len;
121         }
122         printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++,ret);
123     }
124 }

当然也可以先在build函数做一些改动，这样在pushup时就不用考虑l==r的情况了。

下面是修改了的build函数

View Code

 1 void build(int l,int r,int rt)
 2 {
 3     setree[rt].cnt=0;
 4     setree[rt].len=0;
 5     if(l==r){
 6     setree[rt<<1].len=0;
 7     setree[rt<<1|1].len=0;
 8     return;
 9     }
10     int m=(l+r)>>1;
11     build(lson);
12     build(rson);
13 }