hdu 1542 Atlantis 扫描线入门

缘起

入门学习扫描线算法~ hdu 1542 Atlantis

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
二维平面有n个平行于坐标轴的矩形,现在要求出这些矩形的总面积. 重叠部分只能算一次.

【输入】
多样例. 每个样例开始于一个整数n(1<=n<=100), 表示矩形的个数. 然后是n行, 每行四个浮点数
0<=x1<x2<=1e5;0<=y1<y2<=1e5
(x1,y1)和(x2,y2)分别是矩形左上角和右下角的顶点坐标.
样例以n=0结束.

【输出】
对每个样例, 输出总面积（精确到小数点第二位）. 具体格式参见样例

【样例输入】
2
10 10 20 20
15 15 25 25.5
0

【样例输出】
Test case #1
Total explored area: 180.00 

【限制】
1s

本题是扫描线的经典入门题. 本文参阅了 【1】（原理部分讲的很棒! 秒懂~）, 吸收了【1】的营养.

关于扫描线算法, 我直接盗用leetcode上的抽象介绍

1
2
3
4
5
在计算几何中，扫描线算法（Sweep Line Algorithm）或平面扫描算法（Plane Sweep Algorithm）是一种算
法范例，它使用虚拟扫描线或扫描面来解决欧几里德空间中的各种问题。它是计算几何中的关键技术之一。

这种算法背后的想法是想象一条线（通常是一条垂直线）在平面上扫过或移动，在某些点停止。几何操作仅限于几何对
象，无论何时停止，它们都与扫描线相交或紧邻扫描线，并且一旦线穿过所有对象，就可以获得完整的解。

扫描线算法在计算机图形学（程序员的三大浪漫之三）中有重要应用——如何将内存中的计算机图形变换到显存中去（显存中的计算机图形是一个二维像素点阵, 而内存中的计算机图形仅仅是若干个变量数据而已.）

好了, 回到本题.

首先, 样例数据给出的图是

要求图中两个矩形覆盖的面积. 首先我们将矩形的上下边分为上位边(即y坐标大的那条平行于x轴的边),和下位边(y坐标小的平行于x轴的边).然后我们把所有矩形的上下位边按照他们y坐标从小到大排序,可以得到4条扫描线（红色的线段）:

又因为上面2个矩形有4个不同的浮点数x坐标,所以我们需要把x坐标离散化,这样才能用线段树来维护信息（所以说，扫描线算法总是离不开线段树的, 学习扫描线的基础就是线段树）. 假设10,15,20,25 （本题的数据）是已经离散化好了的.

我们可以看到, 4个x坐标将本题的矩形向X轴的投影分成了三段. 分别是树节点1、树节点2、树节点3. 这三个节点是X轴坐标10、15、20、25 离散化变成1、2、3、4 之后, 对 [1,4]构建区间线段树（【2】）（而非点线段树）之后的三个(叶子)节点. 即像下面这个样子的线段树

然后我们Y坐标从小到大的顺序读入每条扫描线, 即按照扫描线1–>扫描线2–>扫描线3–>扫描线4这样的顺序考察所有的扫描线. 注意, 每条扫描线都有自己能覆盖的X轴的范围——例如扫描线1覆盖X轴的范围是 [10,20].

扫描线2覆盖X轴的范围是[15,25]…

这里特别要注意如果我们读入的扫描线是矩形的下位边,那么我们就使得该扫描线能包含的树节点的属性cnt+1,如果是上位边,那么该扫描线能包含的树节点的cnt属性就-1.所以如果树节点的cnt属性=0时,表示该树节点控制的X轴区间范围没有被覆盖,而如果树节点的cnt属性>0 就表示该树节点控制的X轴区间范围仍然被cnt条扫描线覆盖着.

下面来演示一下如何使用扫描线计算总面积——从而解决本题

首先是读入第一条扫描线

扫描线1是一条下位边. 扫描线1的覆盖区间范围是 [10,20]

ps: 这里插一段话哈~ 又讲回上面的离散化主题. 其实X轴的坐标是 10,15,20,25, 离散化完毕之后是 1,2,3,4. 而扫描线1覆盖的范围是[10,20]其实就是区间 [1,3]嘛~ 所以离散化应用到本题具体是这么回事~

好了, 言归正传. 扫描线1覆盖的范围是[1,3] （其实就是原题数据范围的 [10, 20]），将[1,3]压入X轴范围的[1,4]构建的区间线段树（注意, 本题而言, 适用于区间线段树而不是点线段树, 参见【2】，这里[1,4] 对应原题数据范围的 [10, 25]）, 则就知道线段树中的[1,2]和[2,3]两个节点会被 [1,3]覆盖, 则这两个树节点的cnt属性+1.

​

而迄今为止读入的扫描线的覆盖范围变成了[10,20]（即离散化之后的[1,3]），而第一条和第二条扫描线的高度差是5, 所以面积新增是 5*10（当前扫描线覆盖范围）= 50， 即增加面积1的面积是50

下面读入第二条扫描线:

由于第二条扫描线也是下位边, 而且第二条扫描线的X轴覆盖范围是 [15, 25] ，即离散化之后的 [2,4], 它覆盖的树节点是[2,3], [3,4]. 即树节点2和树节点3. 所以这两个树节点的cnt属性+1. 这导致我们迄今为止读入的扫描线的覆盖范围变成了[1,4], 即离散化之前的 [10,25]. 而第三条扫描线的高度是20, 所以第三条和第二条扫描线的高度差是20-15=5, 所以增加面积2的面积是 5*(25-10)=75, 其中 25-10是当前扫描线的覆盖范围. 即增加面积2的面积是75

下面我们要读第三条扫描线了:

由于第三条扫描线是区间[10,20]的上位边,所以对应区间的cnt要-1, 具体而言就是 [10,20]离散化之后是 [1,3], 压入线段树到了 [1,2]和[2,3]两个叶子节点. 然后将这两个叶子节点的cnt属性-1. 则[1,2]的cnt变成0, 而[2,3]的cnt变成2-1=1（注意, [2,3]被扫描线1和扫描线2覆盖了两次）. 而[20,25]即 [3,4]的cnt没变, 依旧是1. 所以当前扫描线覆盖的范围是 [2,4] 即 [15, 25]. 所以扫描线的读入导致增加的面积是上图的增加面积3, 其面积为 (25-15)*(25.5-20)=55

所以2个矩形覆盖的面积三块面积之和： 50+75+55=180.

上面的过程就是扫描线算法用于求区域面积. 其实和数学里面的求定积分有点像（手动逃）~

原理讲完了, 下面讲讲代码实现

首先建立一个扫描线结构体 SweepLine, 它的属性有

  1. l

    表示扫描线的左端x坐标

  2. r

    表示扫描线的右端x坐标

  3. h

    表示扫描线的高度

  4. tag

    为1或-1,标记扫描线是矩形的上位还是下位边.

我们首先顺次读入所有矩形的信息,每读入一个矩形信息我们就更新两条扫描线,并且把矩形的4个顶点的2个x坐标放入X[MAXN]数组中,

然后我们对node按h值从小到大排序（扫描线升高）. 对X离散化处理（仿效【3】中的离散化技巧, 要能O(1)知道原X数组离散化之后的值, 也能O(1)知道离散化之后的值对应原数组中的值）.

对离散化之后的X范围建立（区间）线段树. 线段树节点信息参见下面的代码.

代码风格和【4】基本保持一致. 当然也和【5】保持一致

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const int maxn = 2005;
struct SweepLine // 扫描线的数据结构
{
	double l,r,h;
	bool tag;  // true 表示是下位边, false 表示是上位边
	int idx; // 排序之前在sl中的索引
	bool operator <(SweepLine &o)
	{
		return h<o.h;
	} // 按照扫描线的高度h升序排序
}sl[maxn];

double x[maxn], y[maxn],ans; // 矩形的横坐标, y是x的离散化结果(效仿【3】的离散化技巧)

int n, num, xx[maxn]; // num是离散化之后x坐标的个数

void discrete()
{
	sort(y,y+2*n);
	num = unique(y, y+2*n) - y;
	for (int i = 0; i<2*n; i++)
	{
		xx[i] = lower_bound(y,y+num, x[i])-y;
	} // 离散化之后, x变成0,...,num-1了,但是在xx中保存(这主要是因为x是double数组导致的)
}

struct SegmentTreeNode
{
	int begin, end, mid;
	double len; // len属性表示当前节点对应的区间的长度
	int cnt; // 当前区间被覆盖的次数
	double sum; // 当前节点对应区间[begin,end]中被扫描线们覆盖的总长度,sum属于业务字段
}segmentTree[maxn<<2];

void build(int begin, int end, int cur)
{
	segmentTree[cur].begin = begin, segmentTree[cur].end = end, segmentTree[cur].mid = begin+end>>1, segmentTree[cur].len = y[end]-y[begin];
	segmentTree[cur].cnt = 0, segmentTree[cur].sum = 0;
	if (begin +1== end) // 区间线段树的根节点是单位长度的区间
	{
		return;
	}
	int mid = segmentTree[cur].mid;
	build(begin, mid, cur<<1);
	build(mid, end, cur<<1|1); // 区间线段树就不是mid+1而是mid
}

void pushdown(int i)
{
	if (segmentTree[i].cnt>0) // 下推懒加载标记前提是你得有懒加载标记啊~ 不然你下推个屁啊~
	{
		segmentTree[i<<1].cnt +=  segmentTree[i].cnt;
		segmentTree[i<<1|1].cnt += segmentTree[i].cnt; // 继承父辈的衣钵
		segmentTree[i].cnt = 0;
	}
}

double getsum(int i) // 统计节点segmentTree[i]对应的区间中还被覆盖的长度
{
	return segmentTree[i].cnt?segmentTree[i].len:segmentTree[i].sum; // 如果懒加载, 则直接返回区间的长度, 否则返回精确的sum域
}

void updata(int begin, int end, int cur, int d)
{
	if (segmentTree[cur].begin==begin && segmentTree[cur].end == end)
	{
		if (segmentTree[cur].cnt + d>0 || begin+1==end) // 不能减小到<=0还懒加载直接return, 减小到0了, 如果直接return掉而不下推当getsum用到本节点的时候是不正确的答案. 所以<=0直接return掉是不对的,所以这里>0才能延迟加载, 否则要立即更新当前节点的sum域,当然,到了叶子节点是不得不返回的.
		{
			segmentTree[cur].cnt+=d;
			return; // 延迟更新sum域
		}
	}
	pushdown(cur); // 下推延迟标记
	int mid = segmentTree[cur].mid;
	if (end<=mid)
	{
		updata(begin, end, cur<<1,d);
	}
	else if (begin>=mid)
	{
		updata(begin, end, cur<<1|1,d);
	}
	else
	{
		updata(begin,mid,cur<<1,d);
		updata(mid, end, cur<<1|1,d);
	}
	segmentTree[cur].sum = getsum(cur<<1)+getsum(cur<<1|1); // 立即更新sum域
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	while(scanf("%d", &n), n)
	{
		++kase;
		memset(segmentTree, 0, sizeof(segmentTree));
		for (int i = 0;i<2*n; i+=2)
		{
			double x1,y1,x2,y2;
			scanf("%lf%lf%lf%lf", &x1, &y1,&x2, &y2);
			sl[i].l = x1, sl[i].r = x2, sl[i].h = y1, sl[i].tag = true; // 下位边
			sl[i].idx = i;
			y[i] = x[i] = x1;
			sl[i|1].l = x1, sl[i|1].r = x2, sl[i|1].h = y2, sl[i|1].tag = false; // 上位边
			sl[i|1].idx = i;
			y[i|1] = x[i|1] = x2;
		}
		sort(sl, sl+2*n); // 扫描线按照h升序排序
		discrete(); // 将x坐标离散化
		build(0, num-1,1); // 对[0,...,num-1]建立区间线段树
		ans = 0;
		for (int i = 0;i<2*n;i++) // 顺次读入2n条扫描线
		{
			if (sl[i].tag) // 如果是下位边, 它的X坐标范围是 [sl[i].l, sl[i].r],对应离散化之后是 [x[sl[i].idx], x[sl[i].idx+1]]
			{
				updata(xx[sl[i].idx], xx[sl[i].idx+1], 1, 1);
			}
			else // 如果是上位边, 则减少覆盖次数
			{
				updata(xx[sl[i].idx], xx[sl[i].idx+1], 1, -1);
			}
			if (i<2*n-1)
			{
				ans += (sl[i+1].h - sl[i].h) * getsum(1);
			}
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n", kase, ans);
	}
	return 0;
}

ac情况

31018564 2019-10-20 22:35:36 Accepted 1542 15MS 1580K 3737 B G++ yfsyfsyfs

唉~ 每次写线段树延迟更新的代码总是这么费力! 要多加总结, 多加练习才行啊~

吐槽一下: 什么扫描线啊~ 其实扫描线算法就是具体业务背景（计算几何）+线段树，扫描线本质上就是一个线段树~ 线段树根据具体的计算几何问题做延迟更新而已.

参考

【1】https://blog.csdn.net/u013480600/article/details/22548393

【2】https://yfsyfs.github.io/2019/07/14/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%BA%94%E7%94%A8%E4%B9%8B%E7%BA%BF%E6%AE%B5%E8%A6%86%E7%9B%96%E6%80%BB%E9%95%BF%E5%BA%A6%EF%BC%88%E5%8F%A6%E4%B8%80%E7%A7%8D%E5%BB%BA%E6%A0%91%E6%96%B9%E5%BC%8F%EF%BC%89/

【3】https://yfsyfs.github.io/2019/10/15/%E6%B4%9B%E8%B0%B7-P3834-%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91-1%EF%BC%88%E4%B8%BB%E5%B8%AD%E6%A0%91%EF%BC%89/

【4】https://yfsyfs.github.io/2019/10/09/%E8%AE%A1%E8%92%9C%E5%AE%A2-%E9%9A%BE%E9%A2%98%E9%A2%98%E5%BA%93-%E5%B0%8FA%E7%9A%84%E9%A2%98/

【5】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91-fzu-2171-%E9%98%B2%E5%AE%88%E9%98%B5%E5%9C%B0-II/