把矩形求面积做完后就弄这求周长的题了，其实求周长只比求面积多了几个标记而已了，这里的flag判断入边出边的标记比起求面积的代码写的精炼多了，各种小技巧啊~困扰N久不想看的题总算给搞定了~
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
const int N=5100;
struct Node
{
int l, r, cover, num, len;
bool leftc, rightc;
}tree[N<<2];
struct Line
{
int x, y1, y2, flag;
}line[N<<1];
int temp[N<<1], yline[N<<1];
int n;
int cmpt(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int cmpL(const void *a, const void *b)
{
return (*(Line *)a).x - (*(Line *)b).x;
}
int myabs(int a)
{
return a>0?a:-a;
}
void build(int l, int r, int p)
{
tree[p].l= l;
tree[p].r= r;
tree[p].cover= 0;
tree[p].len= 0;
tree[p].num= 0;
tree[p].leftc=tree[p].rightc= 0;
if ( r-l > 1 )
{
int mid= l+r >> 1;
build(l, mid, 2*p);
build(mid, r, 2*p+1);
}
}
void update(int p)
{
if ( tree[p].cover > 0 )
{
tree[p].num= tree[p].leftc = tree[p].rightc = 1;
tree[p].len= yline[tree[p].r] - yline[tree[p].l];
}
else if ( tree[p].r - tree[p].l <= 1)
tree[p].len= tree[p].leftc= tree[p].rightc= tree[p].num= 0;
else
{
tree[p].rightc= tree[(p<<1)+1].rightc;
tree[p].leftc= tree[p<<1].leftc;
tree[p].len= tree[p<<1].len+tree[(p<<1)+1].len;
tree[p].num= tree[p<<1].num+tree[(p<<1)+1].num-tree[(p<<1)+1].leftc*tree[p<<1].rightc;
}
}
void insert(int l, int r, int p, int flag)
{
if ( l <= yline[tree[p].l] && yline[tree[p].r] <= r )
{
tree[p].cover+=flag;
update(p);
return;
}
if ( tree[p].r - tree[p].l <= 1 )
return;
int mid= tree[p].l+tree[p].r >> 1;
if ( l <= yline[mid] )
insert(l, r, p<<1, flag);
if ( yline[mid] < r )
insert(l, r, (p<<1)+1, flag);
update(p);
}
int main()
{
while ( ~scanf("%d", &n) )
{
int i, m= 0;
int x1, x2, y1, y2;
for ( i = 0 ; i < n ; i++ )
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
line[2*i].x= x1;
line[2*i].y1= y1;
line[2*i].y2= y2;
line[2*i].flag= 1;
line[2*i+1].x= x2;
line[2*i+1].y1= y1;
line[2*i+1].y2= y2;
line[2*i+1].flag= -1;
temp[2*i]= y1;
temp[2*i+1]= y2;
}
n <<= 1;
qsort(temp, n, sizeof(int), cmpt);
qsort(line, n, sizeof(Line), cmpL);
yline[0]= temp[0];
for ( i = 1 ; i < n ; i++ )
if ( yline[m] != temp[i] )
yline[++m]= temp[i];
build(0, m, 1);
int ans, last, lines;
insert(line[0].y1, line[0].y2, 1, line[0].flag);
last= ans=tree[1].len;
lines=tree[1].num;
for ( i = 1 ; i < n ; i++ )
{
insert(line[i].y1, line[i].y2, 1, line[i].flag);
ans+=2*lines*(line[i].x-line[i-1].x);
ans+=myabs(tree[1].len-last);
last= tree[1].len;
lines=tree[1].num;
}
printf("%d\n", ans);
}
return 0;
}