扫描线算法

 1 #include 2 #include 3 #include
 4 using namespace std;
 5 const int maxn=1e4+10;
 6 struct node{
 7     int h,l,r,val;
 8 }e[maxn];
 9 int refl[maxn];
10 struct node2{
11     int l,r,len,ysum;
12     int cnt;
13     bool lv,rv;
14 }tree[maxn1];
15 bool cmp(node p,node q){
16     return (p.h!=q.h)?(p.hq.val);
17 }
18 void build(int root,int l,int r){
19     tree[root].l=l;tree[root].r=r;
20     tree[root].cnt=0;tree[root].len=0;tree[root].ysum=0;
21     tree[root].lv=false;tree[root].rv=false;
22     if (l==r) return ;
23     int mid=(l+r)>>1;
24     build(root1,l,mid);
25     build(root1|1,mid+1,r);
26 }
27 void pushdown(int root){
28     if (tree[root].cnt){
29         tree[root].len=refl[tree[root].r+1]-refl[tree[root].l];
30         tree[root].lv=true; tree[root].rv=true;
31         tree[root].ysum=1;
32     }
33     else if (tree[root].l==tree[root].r){
34         tree[root].lv=false; tree[root].rv=false;
35         tree[root].len=0; tree[root].ysum=0;
36     }
37     else{
38         tree[root].len=tree[root1].len+tree[root1|1].len;
39         tree[root].lv=tree[root1].lv;
40         tree[root].rv=tree[root1|1].rv;
41         tree[root].ysum=tree[root1].ysum+tree[root1|1].ysum-tree[root1|1].lv*tree[root1].rv;
42     }
43 } 
44 void update(int root,int xx,int yy,int kk){
45     if (xx=tree[root].r){
46         tree[root].cnt+=kk;
47         pushdown(root);
48         return ;
49     }
50     int mid=(tree[root].l+tree[root].r)>>1;
51     if (yy1,xx,yy,kk);
52     else if (xx>mid) update(root1|1,xx,yy,kk);
53     else{
54         update(root1,xx,mid,kk);
55         update(root1|1,mid+1,yy,kk);
56     }
57     pushdown(root);
58 }
59 int main(){
60     int n,x,y,xx,yy;
61     while (~scanf("%d",&n)){
62         int num=0;
63         for (int i=1;i){
64             scanf("%d%d%d%d",&x,&y,&xx,&yy);
65             e[++num]={y,x,xx,1}; refl[num]=x;
66             e[++num]={yy,x,xx,-1}; refl[num]=xx;
67         }
68         sort(refl+1,refl+1+num);
69         sort(e+1,e+1+num,cmp);
70         int tot=unique(refl+1,refl+1+num)-(refl+1);
71         build(1,1,tot);
72         int ans=0,lastlen=0;
73         for (int i=1;i){
74             int ll=lower_bound(refl+1,refl+1+tot,e[i].l)-refl;
75             int rr=lower_bound(refl+1,refl+1+tot,e[i].r)-refl-1;
76             update(1,ll,rr,e[i].val);
77             ans+=2*tree[1].ysum*(e[i+1].h-e[i].h);
78             ans+=abs(tree[1].len-lastlen);
79             lastlen=tree[1].len;
80         }
81         printf("%d\n",ans);
82     }
83     return 0;
84 }