【理解】线段树——扫描线

103 阅读 0 评论 68 点赞

我是靠谱客的博主感动鸭子，这篇文章主要介绍【理解】线段树——扫描线，现在分享给大家，希望可以做个参考。

原文：http://www.cnblogs.com/kane0526/archive/2013/02/26/2934214.html

题目大意：给你n个矩形，求他们的总面积之和。

解题思路：

这是我写的线段树扫描线第一题，搜狗了一下，说实话网上的解释都很抽象，昨晚用手机百度一下看到了一张让人一看就有灵感的扫描线图，今天找了很久都没找到那张图了，本来还想copy一下给大家分享来着。

哈哈，不过大家别急，为了方便描述，自己动手画了几个。

四条红线为矩形的上下底边，这里我们称之为扫描线（实际编程中不存在，只是一个概念）。

如图所示，要求两个矩形的面积并，可以把矩形分成几个小矩形，最后的面积总和为它们的和。

对于每个小矩形其面积S=长*宽。宽就是两条扫描线之间y的差值，这里留给我们的问题就是如何求长了。

因为x是double型而且比较大，所以首先对x进行离散化，x数组下标对应实际的x。

然后就开始建树了，建树比较简单，主要的问题在于如何进行更新树。我在这里卡了好久，要注意实际的扫描线长度随时可能变化，并不是相同的，唯一不变的就行要更新数的左右区间（即矩形的底边长度）。

因为扫描线是会变的，所以这里才是我们要重点解决的问题，怎么办？哈哈，这里引出我们伟大的标记变量cover，对于每个矩形下底边标记为1，上底边标记为-1。当一根线扫描到下一根线的时候，cover值会覆盖相应的区间，被覆盖的区间flag值会加上此扫描线的cover（可能为正也可能为负）值，这里最好动手自己模拟一下。所以重叠位置（flag>2）就算遇见负的cover它的flag依然是正的！！

重点要提的是：覆盖区间只在总区间上变化，总区间一直保持不变。

PS：还是看不懂的话看着代码理解吧，我就是这样过来的。

对扫描线进行y从小到大排序，然后从下往上扫描。

复制代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lz 2*u,l,mid
#define rz 2*u+1,mid+1,r
const int maxn=4222;
double sum[maxn];
int flag[maxn];
double X[maxn];
struct Node
{
double lx, rx, y;
int s;
Node(){};
Node(double lx_, double rx_, double y_, int s_)
{
lx=lx_, rx=rx_, y=y_, s=s_;
}
bool operator <(const Node &S) const
{
return y<S.y;
}
}line[maxn];
int find(double tmp, int n)
{
int l=1, r=n, mid;
while(l<=r)
{
mid=(l+r)>>1;
if(X[mid]==tmp) return mid;
else if(X[mid]<tmp) l=mid+1;
else r=mid-1;
}
}
void push_up(int u, int l, int r)
{
if(flag[u]) sum[u]=X[r+1]-X[l];
else if(l==r) sum[u]=0;
else sum[u]=sum[2*u]+sum[2*u+1];
}
void Update(int u, int l, int r, int tl, int tr, int c)
{
if(tl<=l&&r<=tr)
{
flag[u]+=c;
push_up(u,l,r);
return ;
}
int mid=(l+r)>>1;
if(tr<=mid) Update(lz,tl,tr,c);
else if(tl>mid) Update(rz,tl,tr,c);
else
{
Update(lz,tl,mid,c);
Update(rz,mid+1,tr,c);
}
push_up(u,l,r);
}
int main()
{
int n,tcase=0;
while(cin >> n,n)
{
int num=0;
memset(flag,0,sizeof(flag));
memset(sum,0,sizeof(sum));
for(int i=0; i<n; i++)
{
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[++num]=Node(x1,x2,y1,1);
X[num]=x1;
line[++num]=Node(x1,x2,y2,-1);
X[num]=x2;
}
sort(X+1,X+num+1);
sort(line+1,line+num+1);
int k=1;
for(int i=2; i<=num; i++)
if(X[i]!=X[i+1]) X[++k]=X[i];
double ans=0;
for(int i=1; i<num; i++)
{
int l=find(line[i].lx,k);
int r=find(line[i].rx,k)-1;
Update(1,1,k,l,r,line[i].s);
ans+=sum[1]*(line[i+1].y-line[i].y);
}
printf("Test case #%dn",++tcase);
printf("Total explored area: %.2lfnn",ans);
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lz 2*u,l,mid
#define rz 2*u+1,mid+1,r
const int maxn=4222;
double sum[maxn];
int flag[maxn];
double X[maxn];
struct Node
{
double lx, rx, y;
int s;
Node(){};
Node(double lx_, double rx_, double y_, int s_)
{
lx=lx_, rx=rx_, y=y_, s=s_;
}
bool operator <(const Node &S) const
{
return y<S.y;
}
}line[maxn];
int find(double tmp, int n)
{
int l=1, r=n, mid;
while(l<=r)
{
mid=(l+r)>>1;
if(X[mid]==tmp) return mid;
else if(X[mid]<tmp) l=mid+1;
else r=mid-1;
}
}
void push_up(int u, int l, int r)
{
if(flag[u]) sum[u]=X[r+1]-X[l];
else if(l==r) sum[u]=0;
else sum[u]=sum[2*u]+sum[2*u+1];
}
void Update(int u, int l, int r, int tl, int tr, int c)
{
if(tl<=l&&r<=tr)
{
flag[u]+=c;
push_up(u,l,r);
return ;
}
int mid=(l+r)>>1;
if(tr<=mid) Update(lz,tl,tr,c);
else if(tl>mid) Update(rz,tl,tr,c);
else
{
Update(lz,tl,mid,c);
Update(rz,mid+1,tr,c);
}
push_up(u,l,r);
}
int main()
{
int n,tcase=0;
while(cin >> n,n)
{
int num=0;
memset(flag,0,sizeof(flag));
memset(sum,0,sizeof(sum));
for(int i=0; i<n; i++)
{
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[++num]=Node(x1,x2,y1,1);
X[num]=x1;
line[++num]=Node(x1,x2,y2,-1);
X[num]=x2;
}
sort(X+1,X+num+1);
sort(line+1,line+num+1);
int k=1;
for(int i=2; i<=num; i++)
if(X[i]!=X[i+1]) X[++k]=X[i];
double ans=0;
for(int i=1; i<num; i++)
{
int l=find(line[i].lx,k);
int r=find(line[i].rx,k)-1;
Update(1,1,k,l,r,line[i].s);
ans+=sum[1]*(line[i+1].y-line[i].y);
}
printf("Test case #%dn",++tcase);
printf("Total explored area: %.2lfnn",ans);
}
return 0;
}