闵可夫斯基和
闵可夫斯基和。[正在施工]
一般人都是由这样一个例题引入学习的，那我们也用这个例题引入，记录。
last update: 2021-12-11 16:35
给定两个凸多边形点集，多次询问向量 \(q\)，问在点集 \(B\) 每个点都移动 \(q\)，两个点集还能有交吗？
对于别的题解，他们大都在花大量笔墨写闵可夫斯基和是什么东西，我觉得这是愚蠢的。
因为我并不能从这个题直观看出来他在求什么的“和”。
考虑这个题，判断两个凸多边形相交情况是较难的，所以我们打算预处理出来可以使这两个多边形有交的向量集合 \(Q\)。
有交的基本情况一定是多边形 \(\mathcal{A,B}\),的某个顶点接触到了另一个的顶点（边相交可以沿边平移）。
所以我们把两个顶点间的向量求出来。如图：
这样我们列出这些向量：
接下来只能感性理解了，对于几个向量，在里面的“影响力”肯定没有在外面的大。
或者这么说明两个向量之间的向量一定合法，有交（毕竟原先的多边形也是凸的，不太可能首末状态有交，中间无交），所以最终的答案一定是一个凸包。
那么问题转换为我们要求这个向量集合组成的凸包 ： \(S=\{q_a-q_b\mid q_a\in A,q_b\in B\}\)。
此时闵可夫斯基和这个概念便可以解释上述问题。
闵可夫斯基和能计算 \(S=\{q_a+q_b\mid q_a\in A,q_b\in B\}\)。
所以对于此题，把 \(B\) 取反，计算闵可夫斯基和即可。
求闵可夫斯基和的方法就是把“边向量”极角排序，然后顺次相连。
证明不是很会，以后再更。
每一个新凸包点都是原先两个凸包的点的和。
注意这些向量加法是原先向量平面上的“点”，而不是边向量，边向量只不过是用来求闵可夫斯基和的。
前面没啥问题把。。。。后面：
假了，寄了
Max卷积如果不是有更好的凸的性质，几乎不可能很快的做出，包括使用闵可夫斯基和。
抱歉可能假了。
其实并没有完全假，
主要就是考虑凸的性质更加厉害。