avatar

扫描线笔记

问题

  1. 给定 n 个矩形的左下角和右上角坐标,求这 n 个矩形覆盖的区域的总面积。
  2. 给定 n 个矩形的左下角和右上角坐标,求这 n 个矩形构成图形的总周长。

如图所示:

封面出现

(数据范围:$n, x_i, y_i\leq500$)

这题普及组选手都能做出来,但还是说一下思路来为下文做铺垫

  1. 开一个二维数组,每个矩形覆盖的位置标 1,其它标 0。

  2. 对于第一个题,统计 1 的数量。

    对于第二个题,统计 1、0 相间的数量。

下面加强数据。

($n \leq 10^5, |x_i|\leq10^9, |y_i|\leq10^9$)

显然上面的做法就不行了。我们需要更强大的算法。

面积扫描线

思想

我们把上图的形状进行一个划分。

Red and Blue and Green

如图所示,三条水平的直线将原图分成了三个部分。

原图的面积就是$\sum\text{某条直线截得图形的长度}\times\text{这条直线与下一条直线间得距离}$

具体求法

使用线段树

由于数据很大,我们需要先离散化。

将边分为两种:上边和下边(顾名思义,上边就是矩形上面的边,下边同理)。每条边赋一个权值,下边赋为 1,上边赋为 -1。

将所有边按照 y 坐标从低到高排序,然后一条一条加到线段树里。

线段树维护以下的几个值:

  • 这个节点管辖的范围 $[l, r + 1]$(从排名第几的坐标到排名第几的坐标)
  • 这个节点覆盖的次数 $cnt$
  • 这个节点管辖的范围被覆盖的长度 $len$

t[1].len即为目前的直线截得图形的长度。

详见代码

代码

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
#include<bits/stdc++.h>
#define ls (u << 1)
#define rs (u << 1 | 1)
#define lc ls, l, mid
#define rc rs, mid + 1, r
#define mid ((l + r) >> 1)
#define int long long
using namespace std;

const int N = 1e6 + 5;
struct Edge {
int l, r, h, w;
friend bool operator <(Edge x, Edge y) { return x.h < y.h; }
} s[N];
struct Segment {
int l, r, len, cnt;
} t[N << 1];
int a[N], n, tot, ans;

inline void build(int u, int l, int r) {
t[u].l = l, t[u].r = r;
if(l == r) return;
build(lc), build(rc);
}

inline void pushup(int u) {
int l = t[u].l, r = t[u].r;
if(t[u].cnt) t[u].len = a[r + 1] - a[l]; //如果这个区间被覆盖了,那么长度就是本区间的长度
else t[u].len = t[ls].len + t[rs].len; //否则为左右子区间长度之和
}

inline void update(int u, int l, int r, int x, int y, int val) {
if(a[l] >= y || a[r + 1] <= x) return;
if(x <= a[l] && a[r + 1] <= y) {
t[u].cnt += val;
pushup(u);
return;
}
update(lc, x, y, val);
update(rc, x, y, val);
pushup(u);
}

signed main() {
ios::sync_with_stdio(0);
cin >> n;
for(register int i = 1; i <= n; i++) {
int x_1, x_2, y_1, y_2;
cin >> x_1 >> y_1 >> x_2 >> y_2;
s[i] = (Edge){x_1, x_2, y_1, 1}; //上边权值为 1
s[n + i] = (Edge){x_1, x_2, y_2, -1}; //下边权值为 -1
a[i] = x_1, a[n + i] = x_2; //离散化数组
}
n *= 2;
sort(s + 1, s + 1 + n); //边按照 y 坐标排序
sort(a + 1, a + 1 + n);
tot = unique(a + 1, a + 1 + n) - a - 1; //点的排序去重
build(1, 1, tot - 1); //建树
for(register int i = 1; i < n; i++) {
update(1, 1, tot - 1, s[i].l, s[i].r, s[i].w); //把每条边塞进线段树
//cout << t[1].len << endl;
ans += t[1].len * (s[i + 1].h - s[i].h); //统计答案
}
cout << ans;
return 0;
}

周长扫描线

还是那张图。

Red and Blue and Green

每条直线对答案的贡献为$|这条直线截得图形的长度-上一条直线截得图形的长度|$

但是不难看出,这样我们只求了水平边对答案的贡献,没有求竖直边对答案的贡献。

目前方法有以下两种。

扫描一次

用线段树维护当前连续被覆盖的线段有多少段(记为 x),那么每条直线对答案的贡献为$|这条直线截得图形的长度-上一条直线截得图形的长度|+2x \times 这条直线与下一条直线距离$

x 的维护方法:记录左端点是否被覆盖,右端点是否被覆盖,再在 pushup() 函数里加一点细节就可以了。

我认为这个方法有些复杂,所以并未使用。

扫描两次[建议使用]

横竖扫描两次就可以了。把所有东西封装在一个 class 里面可以大大减少代码量。

代码

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
#include<bits/stdc++.h>
#define ls (u << 1)
#define rs (u << 1 | 1)
#define lc ls, l, mid
#define rc rs, mid + 1, r
#define mid ((l + r) >> 1)
#define int long long
using namespace std;

const int N = 1e5 + 5;
class ScannerLine {
public:
int a[N], tot = 0, ans = 0, lst = 0, top = 0;
struct Edge {
int l, r, h, w;
friend bool operator <(Edge x, Edge y) {
if(x.h == y.h) return x.w > y.w;
return x.h < y.h;
}
} s[N];
struct Segment {
int l, r, len, cnt;
} t[N];
inline void push(int l, int r, int h, int w) {
//cout << "push()" << endl;
top++;
s[top].l = l;
s[top].r = r;
s[top].h = h;
s[top].w = w;
a[++tot] = l, a[++tot] = r;
}
inline void build(int u, int l, int r) {
t[u].l = l, t[u].r = r;
if(l == r) return;
build(lc), build(rc);
}
inline void pushup(int u) {
int l = t[u].l, r = t[u].r;
if(t[u].cnt) t[u].len = a[r + 1] - a[l];
else t[u].len = t[ls].len + t[rs].len;
}
inline void update(int u, int l, int r, int x, int y, int w) {
if(a[l] >= y || a[r + 1] <= x) return;
if(x <= a[l] && a[r + 1] <= y) {
t[u].cnt += w;
pushup(u);
return;
}
update(lc, x, y, w), update(rc, x, y, w);
pushup(u);
}
inline void init() {
sort(s + 1, s + 1 + top);
sort(a + 1, a + 1 + tot);
//cout << "sort" << endl;
int x = unique(a + 1, a + 1 + tot) - 1 - a;
tot = x;
//cout << "unique" << endl;
build(1, 1, tot - 1);
}
inline int calc() {
init();
//cout << "inited" << endl;
int res = 0;
for(register int i = 1; i <= top; i++) {
update(1, 1, tot - 1, s[i].l, s[i].r, s[i].w);
res += abs(t[1].len - lst); //如上所述
lst = t[1].len;
}
return res;
}
} lev, ver; //水平、竖直方向的扫描线
int n;

signed main() {
ios::sync_with_stdio(0);
cin >> n;
for(register int i = 1; i <= n; i++) {
int x_1, y_1, x_2, y_2;
cin >> x_1 >> y_1 >> x_2 >> y_2;
lev.push(x_1, x_2, y_1, 1), lev.push(x_1, x_2, y_2, -1);
ver.push(y_1, y_2, x_1, 1), ver.push(y_1, y_2, x_2, -1);
}
int ans = lev.calc() + ver.calc();
cout << ans;
return 0;
}

题目

上文的两道题分别是:

  1. 洛谷 P5490 【模板】扫描线
  2. P1856 [USACO5.5]矩形周长Picture
文章作者: SocialZxy
文章链接: http://socialzxy.github.io/2020/04/04/%E6%89%AB%E6%8F%8F%E7%BA%BF%E7%AC%94%E8%AE%B0/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 SocialZxy's Blog

评论