Description
A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.
Input
Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.Output
Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.Sample Input
7 -15 0 5 10 -5 8 20 25 15 -4 24 14 0 -6 16 4 2 15 10 22 30 10 36 20 34 0 40 16
Sample Output
228求解n的矩形的並的周長，兩種方法。
第一種，對橫向縱向分別遍歷，用兩次掃描線，第一次從左到右，離散化y坐標，增加一條邊後，引起總和改變，改變量就是邊的長度，沒改變的就是隱藏在了原來圖形的裡面，沒有形成新的邊，先把所有縱向的邊總計，在統計橫向的邊，最後的結果就是總的邊長。也可以避免求圖形內部的邊。
#include#include #include #include using namespace std; #define maxn 11000 struct node{ int l , r ; int sum ; }cl[maxn<<2]; struct node1{ int k , l , r ; int flag ; }p[maxn] , q[maxn]; int lazy[maxn<<2] , x[maxn] , y[maxn] ; bool cmp(node1 a,node1 b) { return a.k < b.k ; } void push_up(int rt) { if( lazy[rt] ) cl[rt].sum = cl[rt].r - cl[rt].l ; else cl[rt].sum = cl[rt<<1].sum + cl[rt<<1|1].sum ; } void creat(int rt,int l,int r,int *a) { cl[rt].l = a[l] ; cl[rt].r = a[r] ; if( r - l > 1 ) { creat(rt<<1,l,(l+r)>>1,a); creat(rt<<1|1,(l+r)>>1,r,a); push_up(rt); } else cl[rt].sum = 0 ; return ; } void update(int rt,int l,int r,int flag) { if( cl[rt].l == l && cl[rt].r == r ) { lazy[rt] += flag ; push_up(rt); } else { if( cl[rt<<1].r > l ){ int x = min(cl[rt<<1].r,r) ; update(rt<<1,l,x,flag);} if( cl[rt<<1|1].l < r ){ int x = max(cl[rt<<1|1].l,l) ; update(rt<<1|1,x,r,flag);} push_up(rt); } } int main() { int i , j , n , m , x1 , y1 , x2 , y2 , low , ans ; while(scanf("%d", &n)!=EOF) { for(i = 0 ; i < n ; i++) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); p[i].k = x1 ;p[i].l = y1 ;p[i].r = y2 ;p[i].flag = 1 ; p[i+n].k = x2 ;p[i+n].l = y1 ;p[i+n].r = y2 ;p[i+n].flag = -1 ; y[i+1] = y1 ; y[i+n+1] = y2 ; q[i].k = y1 ;q[i].l = x1 ;q[i].r = x2 ;q[i].flag = 1 ; q[i+n].k = y2 ;q[i+n].l = x1 ;q[i+n].r = x2 ;q[i+n].flag = -1 ; x[i+1] = x1 ; x[i+n+1] = x2 ; } ans = 0 ; memset(lazy,0,sizeof(lazy)); sort(y+1,y+(2*n+1)); sort(p,p+2*n,cmp); m = unique(y+1,y+(2*n+1))- (y+1); creat(1,1,m,y); ans = low = 0 ; update(1,p[0].l,p[0].r,p[0].flag); ans += fabs(low-cl[1].sum); low = cl[1].sum ; for(i = 1 ; i < 2*n ; i++) { update(1,p[i].l,p[i].r,p[i].flag); ans += fabs(low - cl[1].sum); low = cl[1].sum ; } sort(q,q+2*n,cmp); sort(x+1,x+(2*n+1)); m = unique(x+1,x+(2*n+1))-(x+1); memset(lazy,0,sizeof(lazy)); memset(cl,0,sizeof(cl)); creat(1,1,m,x); low = 0 ; update(1,q[0].l,q[0].r,q[0].flag); ans += fabs(low-cl[1].sum); low= cl[1].sum ; for(i = 1 ; i < 2*n ; i++) { update(1,q[i].l,q[i].r,q[i].flag); ans += fabs( low - cl[1].sum ); low = cl[1].sum ; } printf("%d\n", ans); } return 0; }
第二種。第一種用了兩次掃描線比較麻煩，也可以只用一次掃描線，離散y坐標，按x從左到右掃描，統計每次總和的更改值，這樣可以得到所有縱向邊的和，對於橫向邊，可以用(p[i].k - p[i-1].k)*cl[1].num*2.前面的(p[i].k - p[i-1].k)相鄰的兩條線段的x坐標的差，cl[1].num代表此時在線段樹中一共有幾條線段，每一條線段，就會增加這條線段的兩個端點帶來的橫邊。所以只要統計到當時有多少段覆蓋的邊，就可以得到那一段的橫向的增加值
統計某一時刻有多少線段覆蓋，可以用lp , rp記錄這一個節點的兩個端點是不是已經覆蓋，如果覆蓋值為1，那麼這一段的num就是1，合並兩個節點的時候，父節點的num等於左右子節點的num和，如果左節點的rp與右節點的lp都是1，那麼父節點的num值減去1。最後得到統計整個線段是由幾個線段組成。
#include#include #include #include using namespace std; #define maxn 11000 struct node{ int k , l , r , flag ; } p[maxn]; struct node1{ int l , r , lp , rp ; int sum , num ; } cl[maxn<<2]; int lazy[maxn<<2] , s[maxn] ; bool cmp(node a,node b) { return a.k < b.k ; } void push_up(int rt) { if( lazy[rt] ) { cl[rt].lp = cl[rt].rp = 1 ; cl[rt].num = 1 ; cl[rt].sum = cl[rt].r - cl[rt].l ; } else { cl[rt].sum = cl[rt<<1].sum + cl[rt<<1|1].sum ; cl[rt].num = cl[rt<<1].num + cl[rt<<1|1].num ; cl[rt].lp = cl[rt<<1].lp ; cl[rt].rp = cl[rt<<1|1].rp ; if( cl[rt<<1].rp && cl[rt<<1|1].lp ) cl[rt].num-- ; } } void creat(int rt,int l,int r) { cl[rt].l = s[l] ; cl[rt].r = s[r] ; cl[rt].lp = cl[rt].rp = 0 ; if( r - l > 1 ) { creat(rt<<1,l,(l+r)/2); creat(rt<<1|1,(l+r)/2,r); push_up(rt); } else cl[rt].num = cl[rt].sum = 0 ; } void update(int rt,int l,int r,int flag) { if( cl[rt].l == l && cl[rt].r == r ) { lazy[rt] += flag ; push_up(rt); } else { if( cl[rt<<1].r > l ){ int x = min(r,cl[rt<<1].r) ; update(rt<<1,l,x,flag);} if( cl[rt<<1|1].l < r ){ int x = max(l,cl[rt<<1|1].l) ; update(rt<<1|1,x,r,flag);} push_up(rt); } return ; } int main() { int n , m , i , j , x1 , y1 , x2 , y2 , ans , low ; while(scanf("%d", &n)!=EOF) { for(i = 0 ; i < n ; i++) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); p[i].k = x1 ; p[i].l = y1 ; p[i].r = y2 ;p[i].flag = 1 ; p[i+n].k = x2 ;p[i+n].l = y1 ; p[i+n].r = y2 ; p[i+n].flag = -1 ; s[i+1] = y1 ; s[i+n+1] = y2 ; } sort(s+1,s+(2*n+1)); sort(p,p+2*n,cmp); m = unique(s+1,s+(2*n+1))-(s+1) ; memset(lazy,0,sizeof(lazy)); creat(1,1,m); ans = 0 ; low = 0 ; update(1,p[0].l,p[0].r,p[0].flag); ans += fabs( low - cl[1].sum ); low = cl[1].sum ; for(i = 1 ; i < 2*n ; i++) { ans += ( p[i].k - p[i-1].k )*cl[1].num*2 ; update(1,p[i].l,p[i].r,p[i].flag); ans += fabs( low - cl[1].sum ); low = cl[1].sum ; } printf("%d\n", ans); } return 0; }
