Hdu 1828
线段树扫描线求周长并，看这篇好文学习：
http://blog.csdn.net/tomorrowtodie/article/details/52048323
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
const int MAXR = 10000 + 5;
const int MAXN = 5000 + 5;
const int Zinf = 100000;
struct xian
{
int l, r, h;
int f;
bool operator<(const xian &b) const
{
return h<b.h;
}
}a[MAXN*2];
int abss(int x) {return x<0 ? -x : x;}
int n;
#define lc (o*2)
#define rc (o*2+1)
#define M ((l+r)>>1)
struct st
{
int col[MAXR*4*4];//覆盖次数
int num[MAXR*4*4];//当前区间分离线段条数
int ls[MAXR*4*4], rs[MAXR*4*4];//左右结点是否被遮挡
int sum[MAXR*4*4];//计算时的有效区间长
void build(int o, int l ,int r)
{
col[o] = 0; num[o] = 0; ls[o] = rs[o] = 0; sum[o] = 0;
if (l==r) return ;
build(lc, l, M);
build(rc, M+1, r);
}
void pushup(int o, int l, int r)
{
if (col[o])
{
num[o] = 1;
ls[o] = rs[o] = 1;
sum[o] = r-l+1;
} else if (l==r)
{
num[o] = 0;
ls[o] = rs[o] = 0;
sum[o] = 0;
} else
{
ls[o] = ls[lc];
rs[o] = rs[rc];
sum[o] = sum[lc] + sum[rc];
num[o] = num[lc] + num[rc] - (rs[lc]&&ls[rc]);
}
}
void update(int o, int l, int r, int x, int y, int c)
{
if (x<=l&&r<=y)
{
col[o] += c;
pushup(o,l,r);
return ;
}
if (x<=M) update(lc, l, M, x, y, c);
if (M<y) update(rc, M+1, r, x, y, c);
pushup(o,l,r);
}
}tree;
int main()
{
while (scanf("%d", &n)==1)
{
int minr = Zinf, maxr = -Zinf;
for (int i=0;i<n;i++)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
minr = min(minr, min(x1,x2));
maxr = max(maxr, max(x1,x2));
a[i*2].l = a[i*2+1].l = x1;
a[i*2].r = a[i*2+1].r = x2;
a[i*2].h = y1; a[i*2+1].h = y2;
a[i*2].f = -1; a[i*2+1].f = 1;
}
sort(a, a+2*n);//数小，不用离散化。
tree.build(1, minr, maxr-1);
int last = 0;
int ans = 0;
for (int i=0;i<2*n;i++)
{
tree.update(1,minr,maxr-1,a[i].l, a[i].r-1, a[i].f);
ans += abss(tree.sum[1]-last);
ans += (a[i+1].h-a[i].h)*2*tree.num[1];
last = tree.sum[1];
}
printf("%d\n",ans);
}
return 0;
}
