[hdu1542] Atlantis (扫描线)

题目传送门

另一个传送到 codevs 3044 的传送门

利用线段树维护一个扫描线。

把每个水平线段都看作区间修改。

从下到上依次扫描，是矩形下边界就添加，是矩形上边界就删除。

线段树维护区间被覆盖了几层，以及区间内被覆盖了的部分的总长。

每次添加线段时，用全部覆盖的长度乘以高度之差得到面积。

挺好写的吧......

卡了一上午，最后发现是离散化挂掉了。

在Dr_J的指导下改成map离散化，就过了，呵呵呵。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<map>
  5 using namespace std;
  6 
  7 int n;
  8 int lb[805],rb[805],lv[805];
  9 double len[805],rx[405];
 10 
 11 struct pct{
 12     double l,r;
 13     double h;
 14     int ll,rr;
 15     int flag;
 16     void ins(double le,double re,double hx,int ll,int rr,int fl)
 17     {
 18         l=le;
 19         r=re;
 20         h=hx;
 21         ll=ll;
 22         rr=rr;
 23         flag=fl;
 24     }
 25 }pc[205];
 26 
 27 bool cmp(pct x,pct y)
 28 {
 29     return x.h<y.h;
 30 }
 31 
 32 bool dcp(double x,double y)
 33 {
 34     return x<y;
 35 }
 36 
 37 map<double,int>M;
 38 
 39 void build(int ord,int l,int r)
 40 {
 41     lb[ord]=l,rb[ord]=r;
 42     lv[ord]=0,len[ord]=0.00;
 43     if(l==r)return;
 44     int mid=(l+r)>>1;
 45     build(ord<<1,l,mid);
 46     build(ord<<1|1,mid+1,r);
 47 }
 48 
 49 void getlen(int ord)
 50 {
 51     if(lv[ord])len[ord]=rx[rb[ord]+1]-rx[lb[ord]];
 52     else if(lb[ord]==rb[ord])len[ord]=0;
 53     else len[ord]=len[ord<<1]+len[ord<<1|1];
 54 }
 55 
 56 void add(int ord,int l,int r,int v)
 57 {
 58     if(l<=lb[ord]&&r>=rb[ord])
 59     {
 60         lv[ord]+=v;
 61         getlen(ord);
 62         return;
 63     }
 64     int mid=(lb[ord]+rb[ord])>>1;
 65     if(l<=mid)add(ord<<1,l,r,v);
 66     if(r>mid)add(ord<<1|1,l,r,v);
 67     getlen(ord);
 68 }
 69 
 70 int main()
 71 {
 72     int cs=1;
 73     while(1)
 74     {
 75         scanf("%d",&n);
 76         if(!n)break;
 77         M.clear();
 78         int cnt=0;
 79         double ans=0.00;
 80         int rnt=0;
 81         int dnt=0;
 82         for(int i=1;i<=n;i++)
 83         {
 84             double le,re,hx,hy;
 85             scanf("%lf%lf%lf%lf",&le,&hx,&re,&hy);
 86             pc[++cnt].ins(le,re,hx,0,0,1);
 87             pc[++cnt].ins(le,re,hy,0,0,-1);
 88             rx[++rnt]=le;
 89             rx[++rnt]=re;
 90         }
 91         sort(rx+1,rx+rnt+1,dcp);
 92         for(int i=1;i<=rnt;i++)
 93         {
 94             if(M.find(rx[i])==M.end())
 95                 M[rx[i]]=++dnt;
 96             rx[dnt]=rx[i];
 97         }
 98         for(int i=1;i<=cnt;i++)
 99         {
100             pc[i].ll=M[pc[i].l];
101             pc[i].rr=M[pc[i].r];
102         }
103         sort(pc+1,pc+cnt+1,cmp);
104         build(1,1,dnt);
105         double btn=0.00;
106         double lst=0.00;
107         for(int i=1;i<=cnt;i++)
108         {
109             ans+=btn*(pc[i].h-lst);
110             add(1,pc[i].ll,pc[i].rr-1,pc[i].flag);
111             btn=len[1];
112             lst=pc[i].h;
113         }
114         printf("Test case #%d
",cs);
115         printf("Total explored area: %.2lf

",ans);
116         cs++;
117     }
118     return 0;
119 }

hdu 1542 Atlantis