Dowemo
0 0 0 0

Similar to area merging, except for how many lines have to be recorded. If the total is 4, it may be 1 2, 3 4, or 1, and the calculation area is different but the calculation perimeter is different.

The following procedures come from online and collect references.

#include <stdio.h>#include <string.h>#include <algorithm>usingnamespacestd;constint N = 5e3+5;#define lson u<<1#define rson u<<1|1struct Seg
{
 int x,y1,y2;
 bool pos; //定义为1和-1最好,可以直接计算 Seg(){}
 Seg(int x,int y1,int y2,int i):x(x),y1(y1),y2(y2),pos(i&1){}
 booloperator <(const Seg& S) const{
 return x <S.x;
 }
}s[N<<1];int y[N<<1];bool del; //用法不好,强制转换//l,r是不需要的,作为参数传递即可struct SegTree
{
 int l,r,cover_cnt,cover_len,interval_cnt;
 bool cover_l,cover_r;
 inlineint mid(){
 return l+r>> 1;
 }
 inlineint len(){
 return y[r] - y[l];
 }
}T[N<<3];void get_len(int u)
{
 if(T[u].cover_cnt> 0)
 T[u].cover_len = T[u].len();
 elseif(T[u].l == T[u].r-1)
 T[u].cover_len = 0.0;
 else T[u].cover_len = T[lson].cover_len + T[rson].cover_len;
}void get_cnt(int u)
{
 if(T[u].cover_cnt> 0)
 {
 T[u].interval_cnt = 1;
 T[u].cover_l = T[u].cover_r = true;
 }
 elseif(T[u].l == T[u].r-1)
 {
 T[u].interval_cnt = 0;
 T[u].cover_l = T[u].cover_r = false;
 }
 else {
 T[u].interval_cnt = T[lson].interval_cnt + T[rson].interval_cnt;
 if(T[lson].cover_r && T[rson].cover_l)
 T[u].interval_cnt --;
 T[u].cover_l = T[lson].cover_l;
 T[u].cover_r = T[rson].cover_r;
 }
}void build(int u,int l,int r)
{
 T[u].l = l, T[u].r = r;
 T[u].cover_len = T[u].cover_cnt = T[u].interval_cnt = 0;
 T[u].cover_l = T[u].cover_r = false;
 int m = T[u].mid();
 if(l!= r-1)
 build(lson,l,m), build(rson,m,r);
}void updata(int u,int l,int r)
{
 if(l == y[T[u].l] && r == y[T[u].r])
 {
 T[u].cover_cnt += del? -1 : 1;
 get_len(u);
 get_cnt(u);
 return ;
 }
 int m = T[u].mid();
 if(r <= y[m])
 updata(lson,l,r);
 elseif(l> = y[m])
 updata(rson,l,r);
 else updata(lson,l,y[m]), updata(rson,y[m],r);
 get_len(u);
 get_cnt(u);
}int solve(int n)
{
 int res = 0, last_depth = 0;
 del = s[0].pos;
 updata(1,s[0].y1,s[0].y2);
 res += T[1].cover_len;
 for(int i=1;i<n;i++)
 {
 res += (s[i].x-s[i-1].x) * T[1].interval_cnt*2;
 del = s[i].pos;
 last_depth = T[1].cover_len;
 updata(1,s[i].y1,s[i].y2);
 res += abs(T[1].cover_len - last_depth);
 }
 return res;
}int main()
{
 int n;
 freopen("a.txt","r",stdin);
 while(~scanf("%d",&n))
 {
 n *= 2;
 for(int i=0;i<n;i+=2)
 {
 int x1,x2,y1,y2;
 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
 s[i] = Seg(x1,y1,y2,i), s[i+1] = Seg(x2,y1,y2,i+1);
 y[i] = y1, y[i+1] = y2;
 }
 sort(y,y+n);
 int nn = unique(y,y+n) - y;
 build(1,0,nn-1);
 sort(s,s+n);
 printf("%dn",solve(n));
 }
 return0;
}



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs