题目链接：http://poj.org/problem?id=1177
题目大意：若干个矩形，求这些矩形重叠形成的图形的轮廓周长。
解题思路：这里引用一下大牛的思路：kuangbin
总体思路:
1.沿X轴离散化建树
2.按Y值从小到大排序平行与X轴的边,然后顺序处理
如果遇到矩形下面那条边则插入到线段树中,遇到矩形上面的边则将相应的边删除掉
根据线段树当前的状态统计长度
第二点是本题的核心思想,偶再举个例:
第一次求出的部分很好理解.
第二次求出的为什么会少了中间那部分.那是因为插入的新线段覆盖了第一条,此时线段树返回的长度是新的那一条的长度,将这个值再减去上次的就少了中间那部分
第三次因为是矩形的上边,所以要删除在那条长的线段.此时的线段树返回的则是第一次的长度,将此值减去第二次返回值,再取其负值就是红色X轴那部分了
最后那条X轴的,再补上就行了。
我写的稍微有点不同，不过大概也就是这个思路了。总结一下就是矩形下位边cnt+1,上位边cnt-1，求tree[1].sum，这些步骤跟求矩形面积并是一样的。
然后按照扫描线从小到大一次跟新，ans+=abs（上一次的测度-更新后的测度）。
然后就按x,y方向扫描线各求一遍，加在一起就是总的周长。（好像还是有点问题，就是重边会出错，不会改啊！！！算了，等以后变强了再来改0 0）
这题我没有离散化，因为数据不是很大也没有小数所以就懒得写了。。。
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<string>
#define LC(a) (a<<1)
#define RC(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N=1e4+; struct Node{
int l,r,cnt,sum;//sum为测度
}tree[N**]; struct node{
int l,r,h,flag;
node(){}
node(double a,double b,double c,double d){
l=a;r=b;h=c;flag=d;
}
}a[N],b[N]; bool cmp(node a,node b){
return a.h<b.h;
}
//因为每条线段对应删除的线段是严格出现的，不需要Lazy也就不需要pushdown（）
void pushup(int p) {
if(tree[p].cnt>)
tree[p].sum=tree[p].r-tree[p].l+;
else if(tree[p].l==tree[p].r)
tree[p].sum=;
else
tree[p].sum=tree[LC(p)].sum+tree[RC(p)].sum;
} void build(int p,int l,int r){
tree[p].l=l;
tree[p].r=r;
if(l==r){
tree[p].cnt=tree[p].sum=;
return;
}
build(LC(p),l,MID(l,r));
build(RC(p),MID(l,r)+,r);
pushup(p);
} void update(int p,int l,int r,int cnt){
if(l>tree[p].r||r<tree[p].l)
return;
if(l<=tree[p].l&&r>=tree[p].r&&tree[p].cnt!=-){
tree[p].cnt+=cnt;
pushup(p);
return;
}
update(LC(p),l,r,cnt);
update(RC(p),l,r,cnt);
pushup(p);
} int main(){
int n;
while(~scanf("%d",&n)){
int m1=,m2=;
for(int i=;i<=n;i++){
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1+=N,x2+=N,y1+=N,y2+=N;//防止x,y出现负数
a[++m1]=node(x1,x2,y1,);
b[m1]=node(y1,y2,x1,);
a[++m1]=node(x1,x2,y2,-);
b[m1]=node(y1,y2,x2,-);
}
sort(a+,a++m1,cmp);
sort(b+,b++m1,cmp);
//自下往上扫描一遍
build(,,*N-);
int ans=;
for(int i=;i<=m1;i++){
int last=tree[].sum;
int l=a[i].l;
int r=a[i].r-;
update(,l,r,a[i].flag);
ans+=abs(tree[].sum-last);
}
//自左往右扫描一遍
build(,,*N-);
for(int i=;i<=m1;i++){
int last=tree[].sum;
int l=b[i].l;
int r=b[i].r-;
update(,l,r,b[i].flag);
ans+=abs(tree[].sum-last);
}
printf("%d\n",ans);
}
return ;
}