Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.
The corresponding boundary is the whole set of line segments drawn in Figure 2.
The vertices of all rectangles have integer coordinates.
InputYour 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.
0 <= number of rectangles < 5000
All coordinates are in the range −10000,10000−10000,10000 and any existing rectangle has a positive area.
Please process to the end of file.OutputYour 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
非常典型的扫描线求周长的问题。想法与求面积很大程度上是相同的，区别是：线段树结点维护区间“底边”长度，“底边”长度发生变化时，变化值的大小加到周长中（这是底边算在周长中的），同时记录每个时刻竖边个数，每次加上相差高度*个数（这是竖边算在周长中的）。其中，记录竖边个数时，为了将“重叠”部分去掉，额外建立bool数组储存某一个区间最左，最右是否是某个矩形的一部分。两个矩形重叠，不管是边刚好接触还是有重叠，都会减少2条竖边。（初始时，只要某区间完整的在某个矩形区间中，竖边数就设为2，在更高一级求和时，如果发现其左子区间的右侧，右子区间的左侧都满足“是某个矩形的一部分”，则说明发生重叠，竖边数-2。
除主要程序以外，还要注意一些线段树的其他问题。这貌似是笔者第一次维护区间有负数的线段树。因为一点小细节的问题做的过程中经历了无数次MLE。实际上问题所在就是对/2 和>>1两个看似一样的操作的了解不够细致。除了效率有微小的区别以外，运算结果在被操作数为负数的时候也有不同。 e.g. (-3)/2=-1 而 （-3）>>1=-2 后者在右移1位时，实际上左补的数取决于操作系统。经测试，在windows和杭电oj评测机的环境下，补的都是1。这样的细节一般情况下无关紧要，但对于本题可能影响就会很大。
在笔者的程序中 如果update某区间为[-1，0] mid按第一种方法算就会为 [-1,0] [0,0] 陷入[-1,0]的死循环，造成MLE的结果。而如果按后者来算 就会为[-1,-1] [0,0]一次就成功走出。显然，后者才是我们想要的结果。
失之毫厘，差之千里。看似不值一提的小地方却可能成为致命的漏洞。以后的学习过程中，一定要更加关注细节。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<string> 6 #include<queue> 7 #include<algorithm> 8 #include<map> 9 #include<cmath> 10 #include<iomanip> 11 #define INF 99999999 12 using namespace std; 13 14 const int MAX=20005; 15 int num[MAX<<2],segnum[MAX<<2],mark[MAX<<2]; 16 bool maxl[MAX<<2],maxr[MAX<<2]; 17 18 19 struct seg 20 { 21 int l,r,h,d; 22 seg(){} 23 seg(int l1,int r1,int h1,int d1):l(l1),r(r1),h(h1),d(d1){} 24 bool operator < (const seg &a)const 25 { 26 if(h==a.h) 27 return d>a.d; 28 return h<a.h; 29 } 30 }s[MAX<<2]; 31 void renew(int l,int r,int k) 32 { 33 if(mark[k]) 34 { 35 num[k]=r-l+1; 36 segnum[k]=2; 37 maxl[k]=maxr[k]=true; 38 return; 39 } 40 else if(l==r) 41 { 42 num[k]=segnum[k]=0; 43 maxl[k]=maxr[k]=false; 44 } 45 else 46 { 47 num[k]=num[2*k]+num[2*k+1]; 48 segnum[k]=segnum[2*k]+segnum[2*k+1]; 49 50 maxl[k]=maxl[2*k];maxr[k]=maxr[2*k+1]; 51 if(maxr[2*k] && maxl[2*k+1]) 52 53 { 54 segnum[k]-=2; 55 56 } 57 } 58 return; 59 } 60 void update(int ul,int ur,int l,int r,int k,int val) 61 { 62 if(l>=ul&&r<=ur) 63 { 64 mark[k]+=val; 65 renew(l,r,k); 66 return; 67 } 68 if(l>=r) 69 return; 70 int mid=(l+r)>>1; 71 if(ul<=mid) 72 update(ul,ur,l,mid,2*k,val); 73 if(ur>mid) 74 update(ul,ur,mid+1,r,2*k+1,val); 75 renew(l,r,k); 76 return; 77 } 78 int n; 79 int main() 80 { 81 int x1,x2,y1,y2; 82 while(cin>>n) 83 { 84 int ge=0; 85 86 int zuo=INF,you=-INF; 87 for(int i=0;i<n;i++) 88 { 89 90 cin>>x1>>y1>>x2>>y2; 91 zuo=min(zuo,x1);you=max(x2,you); 92 s[ge++]=seg(x1,x2,y1,1); 93 s[ge++]=seg(x1,x2,y2,-1); 94 } 95 sort(s,s+ge); 96 int an=0; 97 int last=0; 98 for(int i=0;i<ge;i++) 99 { 100 if(s[i].l<s[i].r) 101 update(s[i].l,s[i].r-1,zuo,you-1,1,s[i].d); 102 103 an+=abs(num[1]-last); 104 an+=segnum[1]*(s[i+1].h-s[i].h); 105 last=num[1]; 106 107 } 108 cout<<an<<" "; 109 } 110 return 0; 111 }