扫描线+线段树解决的是矩形覆盖求面积/周长问题
面积版：
也就是给出若干个矩形，最后求总面积（重点是快速解决覆盖问题）
矩形覆盖
三个矩形叠在一起就会产生重复部分，要怎么解决这个问题呢？
此类问题一般都是用线段树辅助扫描法来计算！
扫描线如下图所示，只要求出每一条扫描线的有效长度，就可以得出该区域的实际面积，最后把所有面积相加，即为该多边形的总面积。
扫描线
所以对于每一个矩形，只需要把矩形转换成上下两条平行线段即可（上边和下边）。
由此我们开一个结构体，记录每一条线段
struct node
{
double l, r, h;//左端点，右端点，y轴(高度)
int d;（记录上下边，上边为-1，下边为1）
} a[50000];
我们可以发现，当矩形非常散乱，或长度太长的时候，我们需要压缩一下各个上下边长来减少时间、空间复杂度，即离散化。
double x[maxn];
……
for(i=1; i<=T; i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
if(y1>y2) swap(y1,y2);
a[m].l=x1, a[m].r=x2, a[m].h=y1, a[m].d=1;
x[m++]=x1;
a[m].l=x1, a[m].r=x2, a[m].h=y2, a[m].d=-1;
x[m++]=x2;
}
sort(x, x+m);
sort(a, a+m, cmp);
int len=unique(x, x+m)-x;//去重
//build(1, 1, len);
double area=0.0;
for(i=0; i<m; i++)//离散化各点，并更新线段树
{
int l=lower_bound(x,x+len,a[i].l)-x+1;
int r=lower_bound(x,x+len,a[i].r)-x;//左闭右开，与普通的线段树记录点不同，这里记录的是线段
//update(1, l, r, a[i].d);
//area+=(a[i+1].h-a[i].h)*tree[1].len;//tree[1]是整个区间,tree[1].len是整个区间的有效长度
}
由于我们要多次求取各个扫描线的有效长度，所以这里采用线段树的方法来求取。
那么问题来了，我们怎么知道那些线段要记录，哪些线段不必记录，或者是要清除呢？
这里我们的上下边的标记就发挥作用了
我们用s来记录标记之和，然后我们可以发现，当S==0时，有效长度为0，即清除该边界。
S的值
整个区间的有效长度
考虑到线段树，这里整个区间的有效长度即为tree[1].len;
线段树的构建
struct Node
{
int tl, tr;
int s;//该节点被覆盖的情况（是否完全覆盖）
double len;//该区间被覆盖的总长度
} tree[50000];
void build(int id, int tl, int tr)
{
tree[id].tl=tl;
tree[id].tr=tr;
tree[id].s=0;
tree[id].len=0;
if(tl==tr) return;
else
{
int tm=(tl+tr)/2;
build(id*2, tl, tm);
build(id*2+1, tm+1, tr);
}
}
void pushup(int id)
{
if(tree[id].s)//去重
{
tree[id].len=x[tree[id].tr]-x[tree[id].tl-1];//tree[id].len=x[tree[id].tr+1-1]-x[tree[id].tl-1];加1是因为左闭右开，计算的时候要加回去，减1是因为x[ ]数组是从0开始建立的，而tree[ ]是从1开始建立的！
}
else if(tree[id].tl==tree[id].tr)//点
{
tree[id].len=0;
}
else
{
tree[id].len=tree[id*2].len+tree[id*2+1].len;
}
}
线段树插入新的线段
void update(int id, int ql, int qr, int xx)
{
int tl=tree[id].tl;
int tr=tree[id].tr;
if(ql<=tl && tr<=qr)
{
tree[id].s+=xx;
pushup(id);
return;
}
int tm=(tl+tr)/2;
if(tm>=ql) update(id*2, ql, qr, xx);
if(tm<qr) update(id*2+1, ql, qr, xx);
pushup(id);
}
这里没有pushdown，这是因为pushup两个作用
Ⅰ合并处理父节点的作用；
Ⅱ删除线段的作用（该标记线段的儿子一定为0，即父节点清零，即删除线段）；
矩形覆盖求面积问题
总代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
double x[50000];
struct node
{
double l, r, h;
int d;
} a[50000];
struct Node
{
int tl, tr;
int s;//该节点被覆盖的情况（是否完全覆盖）
double len;//该区间被覆盖的总长度
} tree[50000];
void build(int id, int tl, int tr)
{
tree[id].tl=tl;
tree[id].tr=tr;
tree[id].s=0;
tree[id].len=0;
if(tl==tr) return;
else
{
int tm=(tl+tr)/2;
build(id*2, tl, tm);
build(id*2+1, tm+1, tr);
}
}
void pushup(int id)
{
if(tree[id].s)//去重
{
tree[id].len=x[tree[id].tr]-x[tree[id].tl-1];
}
else if(tree[id].tl==tree[id].tr)//点
{
tree[id].len=0;
}
else
{
tree[id].len=tree[id*2].len+tree[id*2+1].len;
}
}
void update(int id, int ql, int qr, int xx)
{
int tl=tree[id].tl;
int tr=tree[id].tr;
if(ql<=tl && tr<=qr)
{
tree[id].s+=xx;
pushup(id);
return;
}
int tm=(tl+tr)/2;
if(tm>=ql) update(id*2, ql, qr, xx);
if(tm<qr) update(id*2+1, ql, qr, xx);
pushup(id);
}
bool cmp(struct node X, struct node Y)
{
return X.h<Y.h;
}
int main()
{
int T, Case=0;
while(~scanf("%d", &T)&&T)
{
int i, m=0;
for(i=1; i<=T; i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
if(y1>y2) swap(y1,y2);
a[m].l=x1, a[m].r=x2, a[m].h=y1, a[m].d=1;
x[m++]=x1;
a[m].l=x1, a[m].r=x2, a[m].h=y2, a[m].d=-1;
x[m++]=x2;
}
sort(x, x+m);
sort(a, a+m, cmp);
int len=unique(x, x+m)-x;//去重
build(1, 1, len);
double area=0.0;
for(i=0; i<m; i++)//离散化各点，并更新线段树
{
int l=lower_bound(x,x+len,a[i].l)-x+1;
int r=lower_bound(x,x+len,a[i].r)-x;//左闭右开，与普通的线段树记录点不同，这里记录的是线段
update(1, l, r, a[i].d);
area+=(a[i+1].h-a[i].h)*tree[1].len;//tree[1]是整个区间,tree[1].len是整个区间的有效长度
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",++Case, area);
}
return 0;
}
周长版：
通过扫描线辅助我们已经可以求取图形的面积了，那周长又该如何求解呢？
周长不同于面积，周长分为上下两边和左右两边。
求取周长
对于上下两边可以采取和求取面积相同的方法再加点小处理。
★★★ 边长=|本次扫描线的有效长度 - 上一次扫描线的有效长度|
边长
double Perimeter=0.0;
double last=0.0;
for(i=0; i<m; i++)
{
update(1, l, r, a[i].d);
Perimeter+=fabs(tree[1].len-last);
last=tree[1].len;
}
解决完上下边，我们再来看看左右边，难道需要我们再做一条垂直的扫描辅助线？
当然，这里有更加简洁的方法。
首先我们现在改一下线段树保存的属性，我们用如下信息记录线段树的节点：
①l , r : 该节点代表的线段的左右端点坐标
②len : 这个区间被覆盖的长度（即计算时的有效长度）
③s : 表示这个区间被覆盖了几次
④lc , rc : 标记这个节点的左右两个端点是否被覆盖（0表示没有，1表示有）
⑤num :这个区间有多少条线段（这个区间被多少条线段覆盖）
struct Node
{
int tl, tr;
int s;
int len, num;
int lc, rc;
} tree[maxn];
num的作用就是统计有多少个竖直边（一条上下边对应一条竖直边，最后处理再乘以2）。
当然会出现如下3种情况：
3种情况
由此我们可以得出：
tree[id].num=tree[id2].num+tree[id2+1].num-(tree[id2].rc&tree[id2+1].lc);
最后统计总的num，即：Perimeter+=(a[i+1].h-a[i].h)2tree[1].num;
矩形覆盖求周长问题
总代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
double x[50000];
struct node
{
double l, r, h;
int d;
} a[50000];
struct Node
{
int tl, tr;
int s;
int len, num;
int lc, rc;
} tree[50000];
void build(int id, int tl, int tr)
{
tree[id].tl=tl;
tree[id].tr=tr;
tree[id].s=0;
tree[id].len=0;
tree[id].lc=0;
tree[id].rc=0;
tree[id].num=0;
if(tl==tr) return;
else
{
int tm=(tl+tr)/2;
build(id*2, tl, tm);
build(id*2+1, tm+1, tr);
}
}
void pushup(int id)
{
if(tree[id].s)
{
tree[id].len=x[tree[id].tr]-x[tree[id].tl-1];
tree[id].lc=tree[id].rc=1;
tree[id].num=1;
}
else if(tree[id].tl==tree[id].tr)
{
tree[id].len=0;
tree[id].lc=tree[id].rc=0;
tree[id].num=0;
}
else
{
tree[id].len=tree[id*2].len+tree[id*2+1].len;
tree[id].lc=tree[id*2].lc;
tree[id].rc=tree[id*2+1].rc;
tree[id].num=tree[id*2].num+tree[id*2+1].num-(tree[id*2].rc&tree[id*2+1].lc);
}
}
void update(int id, int ql, int qr, int xx)
{
int tl=tree[id].tl;
int tr=tree[id].tr;
if(ql<=tl && tr<=qr)
{
tree[id].s+=xx;
pushup(id);
return;
}
int tm=(tl+tr)/2;
if(tm>=ql) update(id*2, ql, qr, xx);
if(tm<qr) update(id*2+1, ql, qr, xx);
pushup(id);
}
bool cmp(struct node X, struct node Y)
{
return X.h<Y.h;
}
int main()
{
int T, Case=0;
while(~scanf("%d", &T)&&T)
{
int i, m=0;
for(i=1; i<=T; i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1,y2);
a[m].l=x1, a[m].r=x2, a[m].h=y1, a[m].d=1;
x[m++]=x1;
a[m].l=x1, a[m].r=x2, a[m].h=y2, a[m].d=-1;
x[m++]=x2;
}
sort(x, x+m);
sort(a, a+m, cmp);
int len=unique(x, x+m)-x;
build(1, 1, len);
double C=0.0;
double last=0.0;
for(i=0; i<m; i++)
{
int l=lower_bound(x,x+len,a[i].l)-x+1;
int r=lower_bound(x,x+len,a[i].r)-x;
update(1, l, r, a[i].d);
C+=fabs(tree[1].len-last);
C+=(a[i+1].h-a[i].h)*2*tree[1].num;
last=tree[1].len;
}
printf("%.0f\n", C);
}
return 0;
}
参考：http://m.blog.csdn.net/tomorrowtodie/article/details/52048323
