题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1828
给你n个矩形，让你求出总的周长。
类似面积并，面积并是扫描一次，周长并是扫描了两次，x轴一次，y轴一次。每次加起来的无非都是新加的边(flag为1)或者是新减的边(flag为-1)，即加起来的是此时的总长度(T[1].val)减去上一次扫到的总长度(last)的绝对值(T[1].val - last)。(注意用c++提交，g++会wa)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 2e4 + ;
struct data {
int l , r , h , flag;
bool operator <(const data& cmp) const {
return h < cmp.h;
}
}x[MAXN] , y[MAXN];
struct segtree {
int l , r , val , add;
}T[MAXN << ]; int f(int a) {
return (a > ? a : -a);
} void build(int p , int l , int r) {
int mid = (l + r) >> ;
T[p].l = l , T[p].r = r , T[p].add = T[p].val = ;
if(r - l == ) {
return ;
}
build(p << , l , mid);
build((p << )| , mid , r);
} void pushup(int p) {
if(T[p].add) {
T[p].val = T[p].r - T[p].l;
}
else if(T[p].r - T[p].l == ) {
T[p].val = ;
}
else {
T[p].val = T[p << ].val + T[(p << )|].val;
}
} void updata(int p , int l , int r , int add) {
int mid = (T[p].l + T[p].r) >> ;
if(l == T[p].l && T[p].r == r) {
T[p].add += add;
pushup(p);
return ;
}
if(r <= mid) {
updata(p << , l , r , add);
}
else if(l >= mid) {
updata((p << )| , l , r , add);
}
else {
updata(p << , l , mid , add);
updata((p << )| , mid , r , add);
}
pushup(p);
} int main()
{
int n , x1 , x2 , y1 , y2;
while(~scanf("%d" , &n)) {
for(int i = ; i < n ; i++) {
scanf("%d %d %d %d" , &x1 , &y1 , &x2 , &y2);
x1 += 1e4 , x2 += 1e4 , y1 += 1e4 , y2 += 1e4;
if(x1 > x2)
swap(x1 , x2);
if(y1 > y2)
swap(y1 , y2);
int ls = i<< , rs = (i<<)|;
x[ls].l = x1 , x[ls].r = x2 , x[ls].h = y1 , x[ls].flag = ;
x[rs].l = x1 , x[rs].r = x2 , x[rs].h = y2 , x[rs].flag = -;
y[ls].l = y1 , y[ls].r = y2 , y[ls].h = x1 , y[ls].flag = ;
y[rs].l = y1 , y[rs].r = y2 , y[rs].h = x2 , y[rs].flag = -;
}
sort(x , x + n * );
sort(y , y + n * );
build( , , 2e4);
int res = , last = ;
for(int i = ; i < * n ; i++) {
updata( , x[i].l , x[i].r , x[i].flag);
res += f(last - T[].val);
last = T[].val;
}
for(int i = ; i < * n ; i++) {
updata( , y[i].l , y[i].r , y[i].flag);
res += f(last - T[].val);
last = T[].val;
}
printf("%d\n" , res);
}
}