正题

      闵可夫斯基和类型的问题是这样子的，给出两个点集A和B，要你求A+B的凸包大小。

      这个就很有趣了。

      因为A+B中的点集中一共有这么多个点，那么就很烦。

      当然，凸包肯定会存在于A的凸包+B的凸包上。

      但是它也可能出两个凸多边形来卡你啊。

      这时，大救星出现了，闵可夫斯基和。

      我们可以给这个两个点集做一次凸包，然后再从这两个点集中分别x最小中y最小的点开始。

      出来之后，可能是这样的。

      就是M点开始，我们进行找点运动。

      可以感性理解：下一个凸包上的点是或者。前提是已经做好凸包，也就是说，点是逆时针排布的。

      所以这样，我们就可以做出来了。求面积请看第十四节