poj1151Atlantis(离散化+扫描线）

http://www.cnblogs.com/kane0526/archive/2013/02/26/2934214.html这篇博客写的不错主要是图画的不错

求面积并离散化后通过添加矩形的x方向边用线段树不断更新（要求的分割开的）矩形的长和宽

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define maxn 5050
 6 using namespace std;
 7 struct node
 8 {
 9     double lx,rx,y;
10     int s;
11     node(){}
12     node(double a,double b,double c,int d):lx(a),rx(b),y(c),s(d){}
13     bool operator < (const node &S) const
14     {
15         return y<S.y;
16     }
17 }mat[maxn];
18 double que[maxn],sum[maxn];
19 int cnt[maxn];
20 int bin(double x,int n)
21 {
22     int s,e,m;
23     s=0;e=n;
24     while(s<=e)
25     {
26         m = (s+e)/2;
27         if(que[m]==x)
28         return m;
29         else if(que[m]>x)
30         e = m-1;
31         else
32         s = m+1;
33     }
34     return m;
35 }
36 void pushup(int l,int r,int w)
37 {
38     if(cnt[w])
39     sum[w] = que[r+1]-que[l];
40     else if(l==r)
41     sum[w] = 0;
42     else
43     sum[w] = sum[w<<1]+sum[w<<1|1];
44 }
45 void update(int a,int b,int d,int l,int r,int w)
46 {
47     if(a<=l&&b>=r)
48     {
49         cnt[w]+=d;
50         pushup(l,r,w);
51         return ;
52     }
53     int m = (l+r)>>1;
54     if(a<=m)
55     update(a,b,d,l,m,w<<1);
56     if(b>m)
57     update(a,b,d,m+1,r,w<<1|1);
58     pushup(l,r,w);
59 }
60 int main()
61 {
62     int i,k,n,cas=1;
63     double a,b,c,d;
64     while(cin>>n)
65     {
66         if(n==0) break;
67         int num = 0;
68         for(i = 1; i <= n ; i++)
69         {
70             cin>>a>>b>>c>>d;
71             que[num] = a;
72             mat[num++]=node(a,c,b,1);
73             que[num] = c;
74             mat[num++] = node(a,c,d,-1);
75         }
76         sort(que,que+num);
77         sort(mat,mat+num);
78         k = 1;
79         for(i = 1 ; i < num ; i++)
80         {
81             if(que[i]!=que[i-1])
82             que[k++] = que[i];
83         }
84         double ans=0;
85         memset(cnt,0,sizeof(cnt));
86         memset(sum,0,sizeof(sum));
87         for(i = 0 ; i < num-1 ; i++)
88         {
89             int l = bin(mat[i].lx,k-1);
90             int r = bin(mat[i].rx,k-1)-1;
91             if(l<=r)
92             update(l,r,mat[i].s,0,k-1,1);
93             ans+=sum[1]*(mat[i+1].y-mat[i].y);
94         }
95         printf("Test case #%d
Total explored area: %.2f

",cas++,ans);
96     }
97     return 0;
98 }

View Code