掃描線+線段樹解決的是矩形覆蓋求面積/周長問題
面積版：
也就是給出若干個矩形项玛，最后求總面積（重點是快速解決覆蓋問題）
矩形覆蓋
三個矩形疊在一起就會產(chǎn)生重復(fù)部分挂据，要怎么解決這個問題呢仙粱？
此類問題一般都是用線段樹輔助掃描法來計算！
掃描線如下圖所示试疙，只要求出每一條掃描線的有效長度柳弄，就可以得出該區(qū)域的實際面積，最后把所有面積相加两蟀，即為該多邊形的總面積网梢。
掃描線
所以對于每一個矩形，只需要把矩形轉(zhuǎn)換成上下兩條平行線段即可（上邊和下邊）赂毯。
由此我們開一個結(jié)構(gòu)體战虏，記錄每一條線段
struct node
{
double l, r, h;//左端點，右端點党涕，y軸(高度)
int d;（記錄上下邊烦感，上邊為-1，下邊為1）
} a[50000];
我們可以發(fā)現(xiàn)膛堤，當(dāng)矩形非常散亂手趣，或長度太長的時候，我們需要壓縮一下各個上下邊長來減少時間肥荔、空間復(fù)雜度绿渣，即離散化。
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]是整個區(qū)間,tree[1].len是整個區(qū)間的有效長度
}
由于我們要多次求取各個掃描線的有效長度誉帅，所以這里采用線段樹的方法來求取淀散。
那么問題來了，我們怎么知道那些線段要記錄蚜锨，哪些線段不必記錄档插，或者是要清除呢？
這里我們的上下邊的標(biāo)記就發(fā)揮作用了
我們用s來記錄標(biāo)記之和踏志，然后我們可以發(fā)現(xiàn)阀捅，當(dāng)S==0時，有效長度為0针余，即清除該邊界饲鄙。
S的值
整個區(qū)間的有效長度
考慮到線段樹凄诞，這里整個區(qū)間的有效長度即為tree[1].len;
線段樹的構(gòu)建
struct Node
{
int tl, tr;
int s;//該節(jié)點被覆蓋的情況（是否完全覆蓋）
double len;//該區(qū)間被覆蓋的總長度
} 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[ ]數(shù)組是從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兩個作用
Ⅰ合并處理父節(jié)點的作用汛蝙；
Ⅱ刪除線段的作用（該標(biāo)記線段的兒子一定為0，即父節(jié)點清零朴肺，即刪除線段）窖剑；
矩形覆蓋求面積問題
總代碼
#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;//該節(jié)點被覆蓋的情況（是否完全覆蓋）
double len;//該區(qū)間被覆蓋的總長度
} 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]是整個區(qū)間,tree[1].len是整個區(qū)間的有效長度
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",++Case, area);
}
return 0;
}
周長版：
通過掃描線輔助我們已經(jīng)可以求取圖形的面積了，那周長又該如何求解呢鞍盗？
周長不同于面積需了，周長分為上下兩邊和左右兩邊。
求取周長
對于上下兩邊可以采取和求取面積相同的方法再加點小處理般甲。
★★★ 邊長=|本次掃描線的有效長度 - 上一次掃描線的有效長度|
邊長
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;
}
解決完上下邊肋乍，我們再來看看左右邊，難道需要我們再做一條垂直的掃描輔助線敷存？
當(dāng)然墓造，這里有更加簡潔的方法。
首先我們現(xiàn)在改一下線段樹保存的屬性历帚，我們用如下信息記錄線段樹的節(jié)點：
①l , r : 該節(jié)點代表的線段的左右端點坐標(biāo)
②len : 這個區(qū)間被覆蓋的長度（即計算時的有效長度）
③s : 表示這個區(qū)間被覆蓋了幾次
④lc , rc : 標(biāo)記這個節(jié)點的左右兩個端點是否被覆蓋（0表示沒有滔岳，1表示有）
⑤num :這個區(qū)間有多少條線段（這個區(qū)間被多少條線段覆蓋）
struct Node
{
int tl, tr;
int s;
int len, num;
int lc, rc;
} tree[maxn];
num的作用就是統(tǒng)計有多少個豎直邊（一條上下邊對應(yīng)一條豎直邊，最后處理再乘以2）挽牢。
當(dāng)然會出現(xiàn)如下3種情況：
3種情況
由此我們可以得出：
tree[id].num=tree[id2].num+tree[id2+1].num-(tree[id2].rc&tree[id2+1].lc);
最后統(tǒng)計總的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
