Dowemo

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>


using namespace std;



const int N = 5e3+5;



#define lson u<<1


#define rson u<<1|1



struct 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){}


 bool operator <(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;


 inline int mid(){


 return l+r>> 1;


 }


 inline int 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();


 else


 if(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;


 }


 else


 if(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);


 else if(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));


 }


 return 0;


}












Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs