闵可夫斯基和

定义

什么是闵可夫斯基和?
两个凸包$A$,$B$,那么他们的和$A+B=C$,其中,对于$C$中的每个坐标,都有$(x_C,y_C)=(x_A+x_B,y_A+y_B)$.
定义为:
$A+B=\{a+b\rvert a\in A,b\in B\}$
最暴力的解法,便是对$A$中每一个点,都加一遍$B$中的点,复杂度为$O(n*m)$
图呢,长这样:

流程

咋出来的啊?
将$B$按照,从原点到凸包$A$中每个点的向量为方向,移动出来的.
啥??其实长这样:

显然,一个凸包内的向量应该是无穷的.我懒得画了
将$B$按照如图的向量进行移动,就得到了我们要的$C$
但是这显然是不可行的.
我们用肉眼观察法,可以知道,这个$C$是由$A$和$B$的边逆时针首尾相接而成的.这样的话,只需要全领出来,然后接起来就完事了.
就是这样:

void Minkefusiji(point s[], int& cnt, point pl1[], int tail1, point pl2[], int tail2)
{
    s[cnt = 1] = pl1[1] + pl2[1];
    for (int i = 1; i <= tail1; i++)
        pl1[i] = pl1[i + 1] - pl1[i];
    for (int i = 1; i <= tail2; i++)
        pl2[i] = pl2[i + 1] - pl2[i];
    int a1 = 1, a2 = 1;
    while (a1 <= tail1 && a2 <= tail2) {
        ++cnt;
        if ((pl1[a1] ^ pl2[a2]) >= 0)   //叉积
            s[cnt] = s[cnt - 1] + pl1[a1++];
        else
            s[cnt] = s[cnt - 1] + pl2[a2++];
    }
    while (a1 <= tail1)
        ++cnt, s[cnt] = s[cnt - 1] + pl1[a1++];
    while (a2 <= tail2)
        ++cnt, s[cnt] = s[cnt - 1] + pl2[a2++];
}

怎么做的?

• 首先,起点应是两个凸包最左下角的点的和.
• 其次,我们将每个凸包的边改为向量
• 每次和$S[cnt-1]$相加,及在求得的凸包上接边,得到下一个边的终点.
• 对于两个凸包,我们要选择更优的,及叉积的判断.
• 最后,我们再对所得集合进行一次求凸包,就结束了

例题推荐

bzoj 2564集合的面积
JSOI2018战争
解析:JSOI2018战争

注

对于$A-B$,这个等式是这么写的$A-B=\{c\rvert c+B\subseteq A\}$
我们称其为闵可夫斯基差
当然,取反这个骚操作,还是更好用