The red figure is the Minkowski sum of blue and green figures.
©Wikipedia

概念

闵可夫斯基和是两个欧几里得空间的点集的和,以德国数学家闵可夫斯基命名。我们这样定义点集 $A$ 和 $B$ 的闵可夫斯基和:

$$A+B=\{a+b \ | \ a \in A,b \in B \}$$

类似地,闵可夫斯基差可以被定义为:

$$A-B=\{c \ | \ c +B \subseteq A\} $$

计算方法

考虑点集 $A + B$ 的凸包上的每一个点 $c = a + b$,那么 $a$ 一定位于 $A$ 的凸包上,$b$ 一定位于 $B$ 的凸包上。

这样这个凸包可以看做是 $A$ 凸包上一个定点在 $B$ 凸包上转一圈,所有点出现过的位置的集合。

仔细分析这个转一圈的过程,我们发现 $A + B$ 的凸包就是 $A$ 的凸包的边和 $B$ 的凸包的边按极角排序后首尾相连所得图形。

例题

Nagisa

给你三个凸多边形,在它们内部分别取三个点构成一个三角形,记它的重心为 $G$。

现在有 $m$ 个询问,每次询问给定一个点 $(x_i,y_i)$,判断这个点是否属于合法的 $G$。

Tutorial

设三角形三个顶点分别为 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$,重心 $G$ 为 $(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3})$。如果我们忽略其中的分母,就可以发现集合 $G$ 实质上是给定凸多边形的闵可夫斯基和。

凸包的闵可夫斯基和还是个凸包,询问就转化成了:给定一个点的坐标,求它是否在一个凸包内。二分即可。

Solutiuon