poj 1151:

可以说是计算几何的扫描线入门题吧。挺简单的，线段树建树部分要想想。其他就看码力了。

1 //13435314    ooyyloo    1151    Accepted    748K    0MS    G++    2079B    2014-09-12 16:16:35  2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #define mp make_pair  7 #define dbg(x) cout<<#x<<"="<
          
           <
           
             sety; 21 double hashy[maxn]; int hpo; 22 23 //seg tree 24 double sh[maxn<<2]; int cov[maxn<<2]; 25 void build(int k,int l,int r) 26 { 27 sh[k]=cov[k]=0; 28 if (l+1==r) return; 29 int mid=l+r>>1; 30 build(k<<1,l,mid); 31 build(k<<1|1,mid,r); 32 } 33 void update(int k,int l,int r) 34 { 35 if (cov[k]) sh[k]=hashy[r]-hashy[l]; 36 else if (l+1==r) sh[k]=cov[k]?hashy[r]-hashy[l]:0; 37 else sh[k]=sh[k<<1]+sh[k<<1|1]; 38 } 39 void modify(int k,int l,int r,int ll,int rr,int v)//we just care about father 40 { 41 if (l>=ll&&r<=rr) 42 { 43 cov[k]+=v; 44 update(k,l,r); 45 return; 46 } 47 int mid=l+r>>1; 48 if (ll
            
             mid) modify(k<<1|1,mid,r,ll,rr,v); 50 update(k,l,r); 51 } 52 53 54 void init() 55 { 56 nn=n<<1; 57 sety.clear(); 58 59 double x1,y1,x2,y2; 60 for (int i=1;i<=n;i++) 61 { 62 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 63 wu[i].x=x1; wu[i].y1=y1; wu[i].y2=y2; wu[i].v=1; 64 wu[i+n].x=x2; wu[i+n].y1=y1; wu[i+n].y2=y2; wu[i+n].v=-1; 65 sety.insert(y1); sety.insert(y2); 66 } 67 hpo=0; 68 foreach(it,sety) hashy[++hpo]=*it; 69 //for (auto x:sety) hashy[++hpo]=x; 70 } 71 int bs(double d) 72 { 73 int l=1,r=hpo,mid; 74 while (l<=r) 75 { 76 mid=l+r>>1; 77 if (d>hashy[mid]) l=mid+1; 78 else r=mid-1; 79 } 80 return l; 81 } 82 void solve() 83 { 84 ans=0.0; 85 sort(wu+1,wu+1+nn); 86 modify(1,1,hpo,bs(wu[1].y1),bs(wu[1].y2),wu[1].v); 87 for (int z=2;z<=nn;z++) 88 { 89 ans+=sh[1]*(wu[z].x-wu[z-1].x); 90 modify(1,1,hpo,bs(wu[z].y1),bs(wu[z].y2),wu[z].v); 91 } 92 } 93 int main() 94 { 95 for (int tt=1;scanf("%d",&n)!=EOF;tt++) 96 { 97 if (!n) break; 98 init(); 99 build(1,1,hpo);100 solve();101 printf("Test case #%d\n",tt);102 printf("Total explored area: %.2f\n",ans);103 puts("");104 }105 return 0;106 }