闵可夫斯基和学习笔记

· · 个人记录

闵可夫斯基和学习笔记

0. 定义和约定

前置知识：一定的计算几何基础。

我们定义平面直角坐标系当中的点加法：

(a, b) + (c, d) = (a + c, b + d)

听说这种把点当作向量看的东西有个名字，叫做点几何。

1. 闵可夫斯基和

定义两个图形 A, B 的闵可夫斯基和 C = \{a + b | a \in A, b \in B\}。

2. 闵可夫斯基和凸包的求法

因为 Scintilla 太菜并且 OI 中涉及不多，这里只讲解 \rm Minkowski 和的凸包的求法。

引理：两凸包的 \rm Minkowski 和的凸包的边就是原凸包上的边。

证明：设 \rm Minkowski 和的凸包的边集为 S，原来两凸包的边集并为 T，即证明 T = S。设两凸包点集并为 A = \{a_1, a_2, \cdots, a_n\}。

我们首先证明 S \subseteq T。注意到对于任意一条连接 a_i + a_j 和 a_k + a_l 两点的边，点 a_i + a_k 以及 a_j + a_l 与其构成了一个平行四边形，所以它们在这条边的两侧，那么这条边就不可能是凸包的边，所以 S \subseteq T。

有了这个中间结论，要证明原结论，我们只需要说明所有边都要用上。可以考虑这样一种构造方法：把凸包上的边极角排序再顺次相接，显然得到的凸包就是 \rm Minkowski 和的凸包，而它的边正是原来两凸包的边。证毕。

事实上也可以感性理解，求 \rm Minkowski 和的凸包的过程相当于把 B 沿着 A 的边平移，这样平移的过程中形成的边就是 A 的边；两次平移之间形成的边就是 B 的边。

从证明中我们也可以看出 \rm Minkowski 和的凸包的求法了：把原凸包上的边极角排序再顺次相接，有共线的情况再求一次凸包即可。

[JSOI2018] 战争

Description

给定平面直角坐标系中 n 个红点和 m 个蓝点，有 q 次询问，每次给定 dx, dy，把所有蓝点向右平移 dx 个单位、向上平移 dy 个单位，询问红蓝点各自的凸包是否有交。n, m, q \le 10^5。

Solution

设向量 w = (dx, dy)，我们只需要找是否存在分别在两个凸包中的点 a, b，使得 a = b + w。这等价于 w = a - b，即 w 在点集 \{a_i - b_j\} 的凸包内。求出二者的 \rm Minkowski 和的凸包即可。时间复杂度 \mathcal{O}(n + q\log n)。