http://poj.org/problem?id=1177
典型的求周长并的题目，在学习了面积并之后，酝酿了好几天，终于把这周长并的独立的写出来了，扫描线面积并 周长并归根到底还是线段树的应用。用线段树来维护数据
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#define N 51000
using namespace std;
struct num
{
int x1,y1,x2,y2;
}infor[N];
struct Num
{
int x,y1,y2,c;
}line[N];
struct tree
{
int l,r,ly,ry,c;
int ch;
}a[4*N];
int b[N],n,Ba;
bool cmp(Num p1,Num p2)
{
if(p1.x!=p2.x)
{
return p1.x < p2.x;
}else
{
return p1.c>p2.c;
}
}
int main()
{
//freopen("data.txt","r",stdin);
int f();
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%d %d %d %d",&infor[i].x1,&infor[i].y1,&infor[i].x2,&infor[i].y2);
}
int res = 0;
res+=f();
for(int i=1;i<=n;i++)
{
swap(infor[i].x1,infor[i].y1);
swap(infor[i].x2,infor[i].y2);
}
res+=f();
printf("%d\n",res);
}
return 0;
}
void build(int k,int l,int r)
{
a[k].l = l; a[k].r = r;
a[k].c = 0;
a[k].ly = b[l];
a[k].ry = b[r];
a[k].ch = 0;
if(l+1==r)
{
return ;
}
int mid = (l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid,r);
}
void pushup(int k)
{
a[k].ch = a[k<<1].ch+a[k<<1|1].ch+a[k].c;
}
void update(int k,Num p)
{
if(a[k].ly==p.y1&&a[k].ry==p.y2)
{
a[k].c+=p.c;
a[k].ch+=p.c;
return ;
}
if(a[k<<1].ry>=p.y2)
{
update(k<<1,p);
}else if(a[k<<1|1].ly<=p.y1)
{
update(k<<1|1,p);
}else
{
Num e = p;
e.y2 = a[k<<1].ry;
update(k<<1,e);
e = p;
e.y1 = a[k<<1|1].ly;
update(k<<1|1,e);
}
pushup(k);
}
int find(int k,Num p)
{
if(a[k].ly<=p.y1&&a[k].ry>=p.y2&&a[k].ch==0)
{
return 0;
}
if(a[k].ly<=p.y1&&a[k].ry>=p.y2&&a[k].c>0)
{
return p.y2 - p.y1;
}
if(a[k<<1].ry>=p.y2)
{
return find(k<<1,p);
}else if(a[k<<1|1].ly<=p.y1)
{
return find(k<<1|1,p);
}else
{
Num e1 = p;
e1.y2 = a[k<<1].ry;
Num e2 = p;
e2.y1 = a[k<<1|1].ly;
return find(k<<1,e1)+find(k<<1|1,e2);
}
}
int f()
{
int Top = 1;
for(int i=1;i<=n;i++)
{
line[Top].x = infor[i].x1;
line[Top].y1 = infor[i].y1;
line[Top].y2 = infor[i].y2;
line[Top].c = 1;
b[Top++] = infor[i].y1;
line[Top].x = infor[i].x2;
line[Top].y1 = infor[i].y1;
line[Top].y2 = infor[i].y2;
line[Top].c = -1;
b[Top++] = infor[i].y2;
}
sort(b+1,b+Top);
sort(line+1,line+Top,cmp);
build(1,1,Top-1);
int res = 0;
for(int i=1;i<=Top-1;i++)
{
if(line[i].c==-1)
{
update(1,line[i]);
}
res+=(line[i].y2-line[i].y1-find(1,line[i]));
if(line[i].c==1)
{
update(1,line[i]);
}
}
return res;
}