题意：求周长的，把矩形先进行融合后的周长，包括内周长
分析：刚看的时候感觉会跟棘手，让人无从下手，不过学过扫描线之后相信就很简单了吧（扫描线的模板- -），还是不说了，下面是一精确图，可以拿来调试数据
*****************************************************************************************************************
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; #define Lson r<<1
#define Rson r<<1|1 const int MAXN = 2e5+;
const int oo = 1e9+; struct stgmentTree
{///len 保存区间包含的边的长度，cover 保存区间被覆盖的次数, sum保存有多少个不相连的区间段
int L, R, len, cover, sum;
bool lb, rb;///左边和右边是否被覆盖
int mid(){return (R+L)>>;}
}a[MAXN<<];
///dir 等于 1 的时候代表左边，-1时候代表右边，右边会抵消左边
struct Point{int x, y1, y2, dir;}ege[MAXN];
int Hash[MAXN], nh;///保存离散化后的数据，nh表示元素个数 bool cmp(Point n1, Point n2)
{///把边按照x的值从左往右排序
return n1.x < n2.x;
}
///查找一条边的长度, x1 < x2
int findSegLen(int x1, int x2)
{///用下标可以直接检索值
return Hash[x2] - Hash[x1];
}
void buildTree(int r, int L, int R)
{
a[r].L = L, a[r].R = R, a[r].cover=; if(L == R-)return ; buildTree(Lson, L, a[r].mid());
buildTree(Rson, a[r].mid(), R);
}
void pushUp(int r)///合并操作
{///需要先注意本区间是否被覆盖
if(a[r].cover != )
{
a[r].len= findSegLen( a[r].L, a[r].R );
a[r].sum = a[r].lb = a[r].rb = ;
}
else if(a[r].L == a[r].R - )
{
a[r].len = ;
a[r].sum = a[r].lb = a[r].rb = ;
}
else
{///如果本区间未被覆盖，并且不为叶子节点，那么就等于子区间的和
a[r].len = a[Lson].len + a[Rson].len; a[r].lb = a[Lson].lb, a[r].rb = a[Rson].rb;
a[r].sum = a[Lson].sum + a[Rson].sum - (a[Lson].rb & a[Rson].lb);
} }
void upData(int r, int L, int R, int dir)
{
if( a[r].L == L && a[r].R == R )
{
a[r].cover += dir;
pushUp(r); return ;
} if(R <= a[r].mid())
upData(Lson, L, R, dir);
else if(L >= a[r].mid())
upData(Rson, L, R, dir);
else
{
upData(Lson, L, a[r].mid(), dir);
upData(Rson, a[r].mid(), R, dir);
} pushUp(r);
} int main()
{
int N; while(scanf("%d", &N) != EOF)
{
int i, x1, x2, y1, y2, k=, C=, pre=; nh = ; for(i=; i<N; i++)
{
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
ege[k].x=x1, ege[k].y1=y1, ege[k].y2=y2, ege[k++].dir=;///左边y
ege[k].x=x2, ege[k].y1=y1, ege[k].y2=y2, ege[k++].dir=-;///右边y
Hash[nh++] = y1, Hash[nh++] = y2;
} sort(Hash, Hash+nh);///排序去重复
nh = unique(Hash, Hash+nh) - Hash;
///离散化后的数据是从0下标开始的
buildTree(, , nh-); ///对边按照x排序
sort(ege, ege+k, cmp); for(i=; i<k-; i++)
{
int L = lower_bound(Hash, Hash+nh, ege[i].y1) - Hash;
int R = lower_bound(Hash, Hash+nh, ege[i].y2) - Hash; upData(, L, R, ege[i].dir); C += fabs(a[].len - pre) + (ege[i+].x - ege[i].x)*a[].sum * ;
pre = a[].len;
} printf("%d\n", C+pre);
} return ; }