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