求矩形的周长（线段树+扫描线） Picture POJ

题目链接：https://cn.vjudge.net/problem/POJ-1177

题目大意：求矩形外部的周长

具体思路：借用一下bin巨的一张图片。

我们按照y周从下往上的扫描线进行扫描，第一下，求出红色的部分的面积（x轴的长度+当前的y高度和上一个点的高度之差*2）。第二次，我们计算x轴的长度是

上一次被覆盖的x轴的长度-当前的被x轴覆盖的面积，这样的话，就可以避免重复的计算了。

AC代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <string>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <vector>
  8 #include <queue>
  9 #include <stack>
 10 #include <ctime>
 11 #define ll long long
 12 # define lson l,m,rt<<1
 13 # define rson m+1,r,rt<<1|1
 14 using namespace std;
 15 const int maxn = 1000+100;
 16 # define inf 0x3f3f3f3f
 17 struct node
 18 {
 19     int l,r,h;
 20     int d;
 21     node() {}
 22     node(int xx,int yy,int zz,int tt)
 23     {
 24         l=xx;
 25         r=yy;
 26         h=zz;
 27         d=tt;
 28     }
 29     bool friend operator < (node t1,node t2)
 30     {
 31         return t1.h<t2.h;
 32     }
 33 } q[maxn<<2];
 34 int Hash[maxn];
 35 int tree[maxn],lazy[maxn],cnt[maxn];
 36 int lx[maxn],ly[maxn];
 37 void up(int l,int r,int rt)
 38 {
 39     if(lazy[rt])
 40     {
 41         cnt[rt]=1;
 42         lx[rt]=1;
 43         ly[rt]=1;
 44         tree[rt]=Hash[r+1]-Hash[l];
 45     }
 46     else if(l==r)
 47     {
 48         cnt[rt]=0;
 49         tree[rt]=0;
 50         lx[rt]=ly[rt]=0;
 51     }
 52     else
 53     {
 54         cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1]-(lx[rt<<1|1]&ly[rt<<1]);//这个地方注意是左边端点的右定点和右边端点的左定点，因为是需要判断区间是否有相交
 55         tree[rt]=tree[rt<<1]+tree[rt<<1|1];
 56         lx[rt]=lx[rt<<1],ly[rt]=ly[rt<<1|1];
 57     }
 58 }
 59 void update(int l,int r,int rt,int L,int R,int p)
 60 {
 61     if(L<=l&&R>=r)
 62     {
 63         lazy[rt]+=p;
 64         up(l,r,rt);
 65         return ;
 66     }
 67     int m=(l+r)>>1;
 68     if(L<=m)
 69         update(lson,L,R,p);
 70     if(R>m)
 71         update(rson,L,R,p);
 72     up(l,r,rt);
 73 }
 74 int main()
 75 {
 76     int n;
 77     while(~scanf("%d",&n))
 78     {
 79         int num=0;
 80         int x1,y1,x2,y2;
 81         for(int i=0; i<n; i++)
 82         {
 83             scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
 84             q[num]= {x1,x2,y1,1};
 85             Hash[num++]=x1;
 86             q[num]= {x1,x2,y2,-1};
 87             Hash[num++]=x2;
 88         }
 89         sort(Hash,Hash+num);
 90         sort(q,q+num);
 91         int k=1;
 92         for(int i=1; i<num; i++)
 93         {
 94             if(Hash[i]==Hash[i-1])
 95                 continue;
 96             Hash[k++]=Hash[i];
 97         }
 98         memset(cnt,0,sizeof(cnt));
 99         memset(lx,0,sizeof(lx));
100         memset(ly,0,sizeof(ly));
101         memset(tree,0,sizeof(tree));
102         memset(lazy,0,sizeof(lazy));
103         int ans=0;
104         int len=0;
105         for(int i=0; i<num; i++)
106         {
107             int l=lower_bound(Hash,Hash+k,q[i].l)-Hash;
108             int r=lower_bound(Hash,Hash+k,q[i].r)-Hash-1;
109             update(0,k-1,1,l,r,q[i].d);
110             ans+=abs(len-tree[1]);
111               len=tree[1];
112             if(i<num-1)
113                 ans+=2*(q[i+1].h-q[i].h)*cnt[1];
114         }
115         printf("%d
",ans);
116     }
117     return 0;
118 }