这个题算是我的第一个扫描线的题，扫描线算是一种思想吧，用到线段树+离散化。感觉高大上。
主要参考了这位大神的博客。
http://www.cnblogs.com/kuangbin/archive/2012/08/15/2640870.html
HDU1542 Atlantis(线段树:扫描线)
http://acm.hdu.edu.cn/showproblem.php?pid=1542
分析:
首先假设有下图两个矩阵,我们如果用扫描线的方法如何计算它们的总面积呢?
首先我们将矩形的上下边分为上位边(即y坐标大的那条平行于x轴的边),和下位边(y坐标小的平行于x轴的边).然后我们把所有矩形的上下位边按照他们y坐标从小到大排序,可以得到4条扫描线:
又因为上面2个矩形有4个不同的浮点数x坐标,所以我们需要把x坐标离散化,这样才能用线段树来维护信息.所以我们这样离散化:
由上图可知,4个不同的x坐标把x轴分成了3段有效的区间.这里要注意我们线段树中每个叶节点(控制区间[L,L])不是指X[L]坐标,而是指区间[X[L],X[L+1]].线段树中其他节点控制的区间[L,R],也是指的x坐标轴的第L个区间到第R个区间的范围,也就是X[L]到X[R+1]坐标的范围.
然后我们Y坐标从小到大的顺序读入每条扫描线,并维护当前我们所读入的所有扫描线能有效覆盖X轴的最大长度sum[1].这里特别要注意如果我们读入的扫描线是矩形的下位边,那么我们就使得该范围的标记cnt位+1,如果是上位边,那么该范围的cnt就-1.所以如果cnt=0时,表示该节点控制的范围没有被覆盖,只要cnt!=0 就表示该节点控制的几块区间仍然被覆盖.
下面依次读入每条矩阵边,来一一分析,首先是读入第一条矩阵边:
我们读入了矩形1的下位边,那么该区域的cnt就+1=1了,所以该区域[10,20]就被覆盖了,然后可以推出整个区域被覆盖的长度是10.再根据第二条扫描线离第一条扫描线的高度差为5.所以不管你第二条扫描线是哪个矩形的什么边,或者能覆盖到X轴的什么范围,我上图中蓝色的矩形面积肯定是要算到总面积里面去的.即总面积ret+=sum[1]*(扫描线2的高度-扫描线1的高度). (想想看是不是这样).
下面读第二条扫描线:
由于第二条扫描线也是下位边,所以[15,20]和[20,25]的cnt+1.使得我们覆盖的范围变成了[10,25]了,并且第3条扫描线在20高度,所以这次我们必然增加的面积是上面深蓝色的长条=sum[1]*(扫描线3的高度-扫描线2的高度).
下面我们要读第三条扫描线了:
由于第三条扫描线是区间[10,20]的上位边,所以对应区间的cnt要-1,所以使得区间[10,15]的cnt=0了,而[15,20]区间的cnt-1之后变成了1.[20,25]的cnt仍然为1,不变.所以当前覆盖的有效x轴长度为10,即区间[15,25].所以增加的面积是图中褐色的部分.
到此,矩形的面积和就算出来了.由于对于任一矩形都是先读下位边(cnt+1),再读上位边(cnt-1)的,所以在更新线段树的过程中,任意节点的cnt都是>=0的.
贴一下xj学长的代码吧。（主要有注释）
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL __int64
#define lson l, mid, 2*rt
#define rson mid+1, r, 2*rt+1
const int maxn = +;
using namespace std;
int n;
double y[maxn];
struct node
{
int l, r, c; //l, r记录左右节点，c记录覆盖情况
double cnt, lf, rf; //cnt记录这一段当前的长度，lf,rf记录这一段实际的边界
}tr[*maxn];
struct Line
{
double x, y1, y2; //x记录该段x坐标，y1,y2记录该段投影的y边界
int f;
}line[maxn]; //记录在y轴上的投影,f=1表示线段的开始，f=-1表示线段的结束
bool cmp(Line a, Line b)
{
return a.x < b.x;
}
void build(int l, int r, int rt)
{
tr[rt].l = l; tr[rt].r = r;
tr[rt].cnt = tr[rt].c = ;
tr[rt].lf = y[l]; tr[rt].rf = y[r]; //相当于离散化，把实际左右坐标离散成l，r
if(l+==r) return;
int mid = (l+r)/;
build(l, mid, *rt);
build(mid, r, *rt+); //注意是mid,不是mid+1，因为要所有段覆盖
}
void calen(int rt)
{
if(tr[rt].c>) //如果这段被覆盖，就更新这段的长度为实际长度
{
tr[rt].cnt = tr[rt].rf-tr[rt].lf;
return;
}
if(tr[rt].l+==tr[rt].r) tr[rt].cnt = ; //如果这段被撤销，而且是最后的就把长度变为0
else tr[rt].cnt = tr[*rt].cnt+tr[*rt+].cnt; //如果被撤销但不是最后的，就加一下左右
}
void update(int rt, Line e) //加入或者减去一条线段后的更新
{
if(e.y1==tr[rt].lf && e.y2==tr[rt].rf)
{
tr[rt].c += e.f; //改变覆盖情况
calen(rt);
return;
}
if(e.y2<=tr[*rt].rf) update(*rt, e);
else if(e.y1>=tr[*rt+].lf) update(*rt+, e);
else //跨区间的情况
{
Line tmp = e;
tmp.y2 = tr[*rt].rf;
update(*rt, tmp);
tmp = e;
tmp.y1 = tr[*rt+].lf;
update(*rt+, tmp);
}
calen(rt);
}
int main()
{
int i, ca=, cnt;
double x1, x2, y1, y2, ans;
while(~scanf("%d", &n)&&n)
{
cnt = ; ans = ;
for(i = ; i < n; i++)
{
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
line[cnt].x = x1; line[cnt].y1 = y1;
line[cnt].y2 = y2; line[cnt].f = ;
y[cnt++] = y1;
line[cnt].x = x2; line[cnt].y1 = y1;
line[cnt].y2 = y2; line[cnt].f = -;
y[cnt++] = y2;
}
cnt--;
sort(line+, line+cnt+, cmp); //按x从小到大排序
sort(y+, y+cnt+); //按照y排序
build(, cnt, ); update(, line[]);
for(i = ; i <= cnt; i++)
{
ans += tr[].cnt*(line[i].x-line[i-].x); //tr[1].cnt记录全段中当前覆盖的值
update(, line);
}
printf("Test case #%d\n", ca++);
printf("Total explored area: %.2lf\n\n", ans);
}
return ;
}
感觉这代码好棒。
暑假学的，好久没看又忘了，又重新写了一遍，怎么说这题都是我扫描线第一发。
一篇介绍扫描线很好的博客。（http://www.cnblogs.com/scau20110726/archive/2013/04/12/3016765.html）
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 210
using namespace std;
struct Line
{
double x1,x2,y;
int f;
} line[N];
struct node
{
double lf,rf,cnt;
int l,r,c;
} q[*N];
int n,tt;
double X[N];
void add(double x1,double y1,double x2,double y2)
{
line[tt].x1=x1;
line[tt].x2=x2;
line[tt].y=y1;
X[tt]=x1;
line[tt++].f=;
line[tt].x1=x1;
line[tt].x2=x2;
line[tt].y=y2;
X[tt]=x2;
line[tt++].f=-;
}
bool cmp(Line a,Line b)
{
return a.y<b.y;
}
void build(int l,int r,int rt)
{
q[rt].l=l;
q[rt].r=r;
q[rt].cnt=q[rt].c=;
q[rt].lf=X[l];
q[rt].rf=X[r];
if(l+==r) return ;
int mid=(l+r)>>;
build(l,mid,rt<<);
build(mid,r,rt<<|);
}
void calen(int rt)
{
if(q[rt].c>)
{
q[rt].cnt=q[rt].rf-q[rt].lf;
return ;
}
if(q[rt].l+==q[rt].r) q[rt].cnt=;
else q[rt].cnt=q[rt<<].cnt+q[rt<<|].cnt;
}
void update(Line e,int rt)
{
if(e.x1<=q[rt].lf&&e.x2>=q[rt].rf)
{
q[rt].c+=e.f;
calen(rt);
return ;
}
if(e.x2<=q[rt<<].rf) update(e,rt<<);
else if(e.x1>=q[rt<<|].lf) update(e,rt<<|);
else
{
Line tmp=e;
tmp.x2=q[rt<<].rf;
update(tmp,rt<<);
tmp=e;
tmp.x1=q[rt<<|].lf;
update(tmp,rt<<|);
}
calen(rt);
}
int main()
{
int K=;
double x1,x2,y1,y2;
while(scanf("%d",&n)!=EOF&&n!=)
{
tt=;
printf("Test case #%d\n",++K);
for(int i=; i<n; i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
add(x1,y1,x2,y2);
}
sort(X+,X+tt);
sort(line+,line+tt,cmp);
build(,tt-,);
update(line[],);
double sum=;
for(int i=; i<tt; i++)
{
sum+=q[].cnt*(line[i].y-line[i-].y);
update(line[i],);
}
printf("Total explored area: %.2lf\n\n", sum);
}
return ;
}