对于任意两个平面点集 $A,B\subseteq {\mathbb{R}}^2$，它们的闵可夫斯基和定义为

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

闵可夫斯基和并不限于凸多边形。下文只讨论非空凸多边形，并将凸多边形视为包含内部和边界的闭凸集；若 $A,B$ 都是凸集，则 $A+B$ 仍是凸集。

求两个凸多边形的闵可夫斯基和

两个凸多边形的边方向序列按极角归并后，可以得到和多边形的边方向序列。这个对应关系不是“一条输入边保留为一条结果边”：若两个当前边方向相同，应将它们的边向量相加为一条结果边，并同时向后移动；重复点、零边和冗余的共线中间点也应删除。

线性归并要求两个输入已经是规范的凸包：

• 顶点均按逆时针顺序给出，并且末尾不重复首点；
• 删除连续重复点和冗余的共线中间点；
• 分别旋转顶点序列，使 $(y,x)$ 字典序最小的顶点位于开头，从而让两组非零边向量使用同一个极角断点。

设规范后的顶点序列分别为 $a_0,\dots ,a_{n-1}$ 和 $b_0,\dots ,b_{m-1}$，从 $a_0+b_0$ 开始，按极角归并两组边向量并依次求前缀和即可。判断两条边是否应合并时，不能只判断叉积为 $0$，还要确认两者同向；反向平行边的叉积同样为 $0$。全部边处理完后会再次得到起点，返回顶点序列时应删除这个重复终点，并在循环意义下清理冗余的共线中间点。

上述流程以两个至少有三个非共线顶点的二维凸多边形为主。单点与其它集合的和只是平移；全体点共线时应先压缩为线段，并对点、线段等退化情况单独处理，不能继续依赖面积符号或“逆时针多边形”的约定。

若两个输入已经规范化，归并的时间复杂度和结果空间复杂度都是 $O(n+m)$。若将所有边重新做一次比较排序，时间复杂度是 $O((n+m)\log (n+m))$；若输入只是无序点集，还要先求凸包，总时间复杂度为 $O(n\log n+m\log m)$。

求两个凸多边形的最大、最小距离

令两个非空凸多边形对应的点集分别为 $A,B$，并定义

$$D=A-B=A+(-B)=\{\overrightarrow{a}-\overrightarrow{b}\mid \overrightarrow{a}\in A,\overrightarrow{b}\in B\}$$

构造 $-B$ 时，将 $B$ 的每个顶点取相反数即可；这个变换保持逆时针方向，但仍需按前述规则重新旋转起点，才能与 $A$ 的边序列线性归并。

则两者之间的最大、最小距离分别为

$$\underset{\overrightarrow{p}\in D}{max}\Vert \overrightarrow{p}\Vert ,\underset{\overrightarrow{p}\in D}{min}\Vert \overrightarrow{p}\Vert$$

这两个问题的扫描方式不同：

• 范数是凸函数，最大值可以在 $D$ 的某个顶点取得，因此枚举 $D$ 的顶点即可；
• 最近点可能位于边的内部。求最小值时，应先判断原点是否位于 $D$ 的内部或边界上，若是则答案为 $0$；否则枚举 $D$ 的每条边，计算原点到线段的最小距离。若 $D$ 退化为点或线段，则分别计算点距或点到线段的距离。

因此，不能用“只枚举和多边形顶点”的方法同时求最小距离。输入已经规范化时，构造 $D$ 并完成上述扫描的总时间复杂度为 $O(n+m)$。

使用整数坐标时，点的加减、边向量相加、叉积、点积和长度平方都应根据坐标上界选用足够宽的中间类型。在已经由坐标范围证明中间结果不会溢出的前提下，竞赛中常见的 long long 坐标实现可使用 __int128；运算前应先提升类型，不能先在 long long 中溢出再转换。若推导出的范围仍超过 __int128，则需要使用更宽的整数类型或多精度整数。