弄了一天，总算搞懂了扫描线是怎么回事，刚开始的时候在网上搜索，代码基本没有注释，很难看懂，随后搜索到了陈宏的论文，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/