闵可夫斯基和

闵可夫斯基和

定义

两个点集 \(A,B\) 的闵可夫斯基和 \(A+B\) 定义为：

\[A+B=\left \{ a+b | a\in A,b\in B \right \}\]
即把 \(B\) 中的每个点当做向量，然后让 \(A\) 中的点沿着这些向量平移，最终得到的点集就是他们的闵可夫斯基和。
这里我们只讨论凸包的闵可夫斯基和。
举个例子，下面这两个凸包（图是搬的）：

的闵可夫斯基和是（绿色边围起来的）：

性质

根据观察因为我一个都不会证，两个凸包的闵可夫斯基和具有以下性质：

• 两个凸包的闵可夫斯基和还是一个凸包。
  
• 两个凸包的闵可夫斯基和所包含的边集恰好是这两个凸包的边集的并集，并且把这些边极角排序之后直接顺次连接起来即可。
  

实现

因为凸包的边集本身就是排好序的，所以把两个凸包的边集极角排序时可以直接归并，然后以 \(A_1+B_1\) 作为闵可夫斯基和的第一个点，顺次把边接上去即可。
[code]void Minkowski_sum(Point *A,Point *B,Point *c,int &n,int &m,int &num){ //求两个凸包 A,B 的闵可夫斯基和，存在 c 中（A,B 中存的是点）        num=0;        c[++num]=A[1]+B[1];        for(int i=1;i