Area of Simple Polygons

题意：求矩形面积的并
题解：扫描线加线段树同poj1389
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=2002;
 7 int num;
 8 struct Node{
 9     int  l;
10     int  r;
11     int tp;
12     int  y;
13  bool operator <(Node a) const{
14             return y<a.y;
15       }
16 }line[2*maxn];
17 int  arr[2*maxn];
18 struct Edge{
19     int left;
20     int right;
21     int flag;
22     int  sum;
23 }node1[maxn*4];
24 void build(int l,int r,int idx){
25     node1[idx].left=l;
26     node1[idx].right=r;
27     if(l==r){
28         node1[idx].flag=0;
29         node1[idx].sum=0;
30         return;
31     }
32     int mid=(l+r)/2;
33     build(l,mid,idx<<1);
34     build(mid+1,r,idx<<1|1);
35     node1[idx].sum=node1[idx<<1].sum+node1[idx<<1|1].sum;
36 }
37 void update(int l,int r,int f,int idx){
38     if(node1[idx].left==node1[idx].right){
39           node1[idx].flag+=f;
40         if(node1[idx].flag)node1[idx].sum=arr[node1[idx].right+1]-arr[node1[idx].left];
41         if(!node1[idx].flag)node1[idx].sum=0;
42         return ;
43     }
44     int mid=(node1[idx].left+node1[idx].right)/2;
45     if(mid>=r)update(l,r,f,idx<<1);
46     else if(mid<l)update(l,r,f,idx<<1|1);
47     else{
48         update(l,mid,f,idx<<1);
49         update(mid+1,r,f,idx<<1|1);
50     }
51     node1[idx].sum=node1[idx<<1].sum+node1[idx<<1|1].sum;
52 }
53 int binaryserach(int  x){
54    int l,r,mid;
55       l=0,r=num+1;
56       while (r-l>1){
57             mid=(l+r)>>1;
58             if (arr[mid]<=x) l=mid;
59                else r=mid;
60       }
61       return l;
62 }
63 int main(){
64     int n;int  x1,y1,x2,y2;
65     long long ans;
66   while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){
67       if(x1==-1&&x2==-1&&y1==-1&&y2==-1)break;
68         num=0;int cnt=2;
69         line[1].l=x1;line[1].r=x2;line[1].y=y1;line[1].tp=1;
70           line[2].l=x1;line[2].r=x2;line[2].y=y2;line[2].tp=-1;
71           arr[++num]=x1;arr[++num]=x2;
72       while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){
73           if(x1==-1&&x2==-1&&y1==-1&&y2==-1)break;
74           
75           line[++cnt].l=x1;line[cnt].r=x2;line[cnt].y=y1;line[cnt].tp=1;
76           line[++cnt].l=x1;line[cnt].r=x2;line[cnt].y=y2;line[cnt].tp=-1;
77           arr[++num]=x1;arr[++num]=x2;
78       }
79       
80   
81       sort(arr+1,arr+num+1);
82         ans=0;
83       sort(line+1,line+cnt+1);
84       build(1,cnt,1);
85      for(int i=1;i<=cnt;i++){
86           ans+=node1[1].sum*(line[i].y-line[i-1].y);
87           int l=binaryserach(line[i].l);
88           int r=binaryserach(line[i].r)-1;
89            update(l,r,line[i].tp,1);
90       }
91       
92     printf("%I64d
",ans);  
93   }
94 }
View Code