弄了一天，總算搞懂了掃描線是怎么回事，剛開始的時(shí)候在網(wǎng)上搜索，代碼基本沒有注釋，很難看懂，隨后搜索到了陳宏的論文，2頁紙能寫完的東西，他居然可以寫那么長，粗略的掃描了一下，感覺原線段和超元線段的定義很不錯(cuò)，其他的實(shí)在講的有點(diǎn)羅嗦就跳過了。鑒于以后還會(huì)有同樣想要學(xué)習(xí)掃描線的同學(xué)，下面我來簡單的介紹一下掃描線的實(shí)現(xiàn)過程吧，希望對(duì)大家有所幫助。
首先說離散化：因?yàn)橛械臅r(shí)候題目中給出的數(shù)據(jù)范圍可能非常大，如果直接建立成線段樹的話，絕對(duì)超內(nèi)存，怎么辦呢？其實(shí)這里所謂離散化就是把這些數(shù)排列在數(shù)組中，然后用數(shù)組的下標(biāo)來代替這個(gè)數(shù)，這樣我們最多只有N*2個(gè)點(diǎn)
如何求周長？ 那么現(xiàn)在我假設(shè)讀者都明白離散化，以及線段樹了！
具體做法有兩種形式 可以對(duì)x離散也可以對(duì)y 離散！ 我這里以對(duì)y 進(jìn)行離散（這樣可能更符和我們平常的思維方式）
1：首先將矩形的豎邊全部存起來（要用一個(gè)標(biāo)記變量標(biāo)記該邊是否為入邊），然后按照豎邊的X 的大小排好序；
2：在存儲(chǔ)矩形豎邊的同時(shí)要把舉行的Y坐標(biāo)存起來，然后排序，最后去掉重復(fù)的點(diǎn)！
3：建樹了根據(jù)第二步中最后留下來點(diǎn)的個(gè)數(shù)num建立一個(gè)區(qū)間長度為[0,num-1]的線段樹；
4：這步很關(guān)鍵了，把排好序的豎邊從左到右開始掃描了，如果是矩形的左邊那么就插入，要是是矩形的右邊了那么就從線段樹里刪除了！（在這里每次插入和刪除線段樹要維護(hù)好兩個(gè)重要的值，一個(gè)是當(dāng)前線段樹的被覆蓋的區(qū)間長度的總和第二個(gè)是當(dāng)前線段樹中被覆蓋的區(qū)間有多少個(gè)）！
PS:其中這兩句代碼非常重要，讀者可以畫個(gè)簡單的圖進(jìn)行理解，起始的時(shí)候我沒明白要記錄線段段數(shù)的作用，仔細(xì)研究了這部分代碼發(fā)現(xiàn)算線段的段數(shù)是為了求得橫邊的長度，還有一點(diǎn)要注意的是，這棵線段樹要建成節(jié)點(diǎn)為單元線段的形式，即如果區(qū)間為[0,3]
線段樹要建成 [0,3]
/ \
[0,1] [1,3]
/ \
[1,2] [2,3]
這樣，我剛開始的時(shí)候嘗試了一下建成節(jié)點(diǎn)的方式，即節(jié)點(diǎn)是[1,1] [2,2]這樣，結(jié)果發(fā)現(xiàn)統(tǒng)計(jì)區(qū)間段數(shù)根本沒法進(jìn)行，后來參考過網(wǎng)上的代碼發(fā)現(xiàn)要這樣建樹，改了一下就過了，可能平時(shí)對(duì)這種建樹方式還是不太熟悉吧。下面可以開始想想如何才能用掃描線求面積并了，感覺基本思想應(yīng)該差不多。
//POJ 1177
//N個(gè)矩形求總周長
//線段樹+離散化+掃描線
//2010年7月21日19:35:45
//Coded By abilitytao
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 10010
struct STnode //線段樹的節(jié)點(diǎn)
{
int l,r;
int len;//區(qū)間內(nèi)代表的長度
int segnum;//區(qū)間內(nèi)被分成的段數(shù)，不懂的話再結(jié)合代碼看看
int cover;//區(qū)間被覆蓋的次數(shù)
int sum;//區(qū)間中被覆蓋的總長度
bool lcover,rcover;//標(biāo)記左右端點(diǎn)是否被覆蓋，用于合并區(qū)間時(shí)候統(tǒng)計(jì)區(qū)間內(nèi)的離散線段數(shù)
STnode()//初始化
{
l = r = 0;
len = segnum = cover = sum = 0;
lcover = rcover = false;
}
};
STnode ST[MAXN*4];//整棵線段樹
struct Line
{
int st,ed;//豎邊的兩個(gè)y值
int x;//此條邊的x值
bool InOut;//是否為入邊
bool operator<(Line o) const//重載小于符號(hào)
{
return x<o.x;
}
};
Line Yline[MAXN];//存儲(chǔ)豎邊
int Index[MAXN];//存儲(chǔ)離散后的y值
int cnt=0;
int n;//存儲(chǔ)矩形的數(shù)目
void Build(int l,int r,int i)//創(chuàng)建線段樹
{
ST[i].l=l;
ST[i].r=r;
ST[i].cover=0;
ST[i].len=Index[r]-Index[l];
ST[i].segnum=0;
ST[i].sum=0;
ST[i].lcover=ST[i].rcover=false;
//建立線段的時(shí)候進(jìn)行初始化
if(r-l>1)
{
int mid=(l+r)>>1;
Build(l,mid,i*2);
Build(mid,r,i*2+1);
}
}
void GetLen(int i)//求節(jié)點(diǎn)包含的線段總長度
{
if(ST[i].cover>0)
ST[i].sum=ST[i].len;
else if(ST[i].r-ST[i].l>1)
ST[i].sum=ST[i*2].sum+ST[i*2+1].sum;
else
ST[i].sum=0;
}
void GetSegNum(int i)//求該區(qū)間所包含的線段數(shù)總量（就是含有不想交的線段的條數(shù)）
{
if(ST[i].cover>0)
{
ST[i].lcover=ST[i].rcover=true;
ST[i].segnum=1;
}
else if(ST[i].r-ST[i].l>1)
{
ST[i].lcover=ST[i*2].lcover;
ST[i].rcover=ST[i*2+1].rcover;
ST[i].segnum=ST[i*2].segnum+ST[i*2+1].segnum-ST[i*2].rcover*ST[i*2+1].lcover;
}
else
{
ST[i].lcover=ST[i].rcover=false;
ST[i].segnum=0;//特殊處理下葉子節(jié)點(diǎn)
}
}
void Insert(int l,int r,int i)//插入一條線段
{
if(ST[i].l==l&&ST[i].r==r)
ST[i].cover++;
else
{
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)
Insert(l,r,i*2);
else if(l>=mid)
Insert(l,r,i*2+1);
else
{
Insert(l,mid,i*2);
Insert(mid,r,i*2+1);
}
}
GetLen(i);
GetSegNum(i);
}
void Delete(int l,int r,int i)//刪除矩形的右邊
{
if(ST[i].l==l&&ST[i].r==r)
ST[i].cover--;
else
{
int mid=(ST[i].l+ST[i].r)>>1;
if(r<=mid)
Delete(l,r,i*2);
else if(l>=mid)
Delete(l,r,i*2+1);
else
{
Delete(l,mid,i*2);
Delete(mid,r,i*2+1);
}
}
GetLen(i);
GetSegNum(i);
//這個(gè)后序操作非常精彩！
}
int GetIndex(int x)// 返回x的下標(biāo)
{
return lower_bound(Index,Index + cnt,x) - Index;//lower_bound函數(shù)返回一個(gè)元素在容器中的迭代器，數(shù)組可以看成特殊的容器，所以這里返回的迭代器就是指針
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
cnt=0;
int i,j,k;
int x1,x2,y1,y2;
for(i=0;i<n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
Yline[i*2].x=x1;
Yline[i*2+1].x=x2;
Yline[2*i].st=Yline[2*i+1].st=y1;
Yline[2*i].ed=Yline[2*i+1].ed=y2;
Yline[2*i].InOut=true;//標(biāo)記入邊
Yline[2*i+1].InOut=false;
Index[2*i]=y1;
Index[2*i+1]=y2;
}
sort(Index,Index+n*2);
sort(Yline,Yline+n*2);
for(int i=1;i<n*2;i++)//Y數(shù)組去重
{
if(Index[i]!=Index[i-1])
Index[cnt++]=Index[i-1];
}
Index[cnt++]=Index[2*n-1];//這里很容易錯(cuò)!
Build(0,cnt-1,1);
int Ans=0;
int Lsum=0;//上一次記錄的長度，畫個(gè)圖很好理解
for(int i=0;i<2*n-1;i++)
{
if(Yline[i].InOut)
Insert(GetIndex(Yline[i].st),GetIndex(Yline[i].ed),1);
else
Delete(GetIndex(Yline[i].st),GetIndex(Yline[i].ed),1);
//畫個(gè)圖還是很好理解下面這兩行的
Ans+=ST[1].segnum*(Yline[i+1].x-Yline[i].x)*2;
Ans+=abs(ST[1].sum-Lsum);
Lsum=ST[1].sum;
}
//特殊處理最后一條出邊，因?yàn)闆]有下一條豎邊了
Delete(GetIndex(Yline[2*n-1].st),GetIndex(Yline[2*n-1].ed),1);
Ans+=abs(ST[1].sum-Lsum);
printf("%d\n",Ans);
}
return 0;
}special thank to this
URL:http://angels1.0.blog.163.com/blog/static/84580504200893171819117/