参考 http://www.cnblogs.com/kuangbin/archive/2013/04/10/3013437.html
但他是错的
3 0 0 1 2 0 2 1 4 1 1 2 3 12 3 0 1 2 2 2 1 4 2 1 0 3 1 12 如上这两组数据
/*
POJ 1177 矩形周长并，求轮廓周长 这题可以不离散化做的，我做的是离散化以后的 这题和矩形面积并有类似的地方 把矩形变成一条条平行于x轴的线段（当然弄成平行于y轴的也是可以的） 要累加的一个是覆盖的线段长度的变化，还有就是竖直的线段。 离散化以后一定要进行去掉重复的点，因为会影响后面合并的时候。 STL中的unique()函数可以快速去掉相同元素 */ #include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> using namespace std; const int MAXN=10010; struct Node { int l,r; int cnt;//有效长度 int lf,rf;//实际的左右端点 int numseg;//分支数，一个分支对应两条竖线 int c;//记录覆盖情况 bool lcover,rcover; }segTree[MAXN*4]; struct Line { int y1,y2; int x; int f; Line(): x(0), y1(0), y2(0), f(0){} Line(int a, int b, int c, int d): x(a), y1(b), y2(c), f(d){} }line[MAXN]; bool cmp(Line a,Line b) { if(a.x==b.x) return a.f>b.f; //这句非常重要不写会错 return a.x<b.x; } int y[MAXN]; void Build(int i,int l,int r) { segTree[i].l=l; segTree[i].r=r; segTree[i].lf=y[l]; segTree[i].rf=y[r]; segTree[i].cnt=0; segTree[i].numseg=0; segTree[i].c=0; segTree[i].lcover=segTree[i].rcover=false; if(l+1==r)return; int mid=(l+r)/2; Build(i<<1,l,mid); Build((i<<1)|1,mid,r); } void calen(int i) { if(segTree[i].c>0) { segTree[i].cnt=segTree[i].rf-segTree[i].lf; segTree[i].numseg=1; segTree[i].lcover=segTree[i].rcover=true; return; } if(segTree[i].l+1==segTree[i].r) { segTree[i].cnt=0; segTree[i].numseg=0; segTree[i].lcover=segTree[i].rcover=false; } else { segTree[i].cnt=segTree[i<<1].cnt+segTree[(i<<1)|1].cnt; segTree[i].lcover=segTree[i<<1].lcover; segTree[i].rcover=segTree[(i<<1)|1].rcover; segTree[i].numseg=segTree[i<<1].numseg+segTree[(i<<1)|1].numseg; if(segTree[i<<1].rcover&&segTree[(i<<1)|1].lcover)segTree[i].numseg--; } } void update(int i,Line e) { if(segTree[i].lf==e.y1&&segTree[i].rf==e.y2) { segTree[i].c+=e.f; calen(i); return; } if(e.y2<=segTree[i<<1].rf) update(i<<1,e); else if(e.y1>=segTree[(i<<1)|1].lf) update((i<<1)|1,e); else { Line temp=e; temp.y2=segTree[i<<1].rf; update(i<<1,temp); temp=e; temp.y1=segTree[(i<<1)|1].lf; update((i<<1)|1,temp); } calen(i); } int main() { int x1,y1,x2,y2; int n; while(scanf("%d",&n)==1) { int t=0; for(int i=0;i<n;i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); line[t]=Line(x1, y1, y2, 1); y[t++]=y1; line[t]=Line(x2, y1, y2, -1); y[t++]=y2; } sort(line,line+t,cmp); sort(y,y+t); int m=unique(y,y+t)-y;//合并相同元素，这里一点要合并相同元素，否则会WA. Build(1,0,m-1); //Build(1,0,t-1); int ans=0; int last=0; int lines=0; for(int i=0;i<t-1;i++) { update(1,line[i]); ans+=segTree[1].numseg*2*(line[i+1].x-line[i].x); ans+=abs(segTree[1].cnt-last); last=segTree[1].cnt; } update(1,line[t-1]); ans+=abs(segTree[1].cnt-last); printf("%d\n",ans); } return 0; }