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