闵可夫斯基和

yuanzhiteng · 2023-09-08 22:28:04 · 个人记录

一. 闵可夫斯基和（Minkovski）

定义某两个凸包 \mathcal{A}(n),\mathcal{B}(m)，其闵可夫斯基和即为：

形象化地，可以理解成在 \mathcal{A,B} 中各取一点 (x_1,y_1),(x_2,y_2)，那么对应的 (x_1+x_2,y_1+y_2) 就在 \mathcal{S} 内。

即为两个向量的加和。

如下图：

粉色凸包即为原来两个黑色凸包的闵可夫斯基和。

不难发现，两个凸包的 Minkovski 具有以下性质：

因此，只需要将原来两个凸包上的边进行极角归并排序即可。

时间复杂度 \mathcal{O}(n+m)。

代码实现：

struct node{
    double x,y;
};
node operator - (const node &a,const node &b){                                      //向量减法
    return (node){a.x - b.x,a.y - b.y};
}
node operator + (const node &a,const node &b){                                      //向量加法
    return (node){a.x + b.x,a.y + b.y};
}
double operator * (const node &a,const node &b){                                    //向量外积
    return a.x * b.y - a.y * b.x;
}
int n,m,q;
node a[maxn],b[maxn],A[maxn],B[maxn];                                               //A,B存放原凸包
node S[maxn];                                                                       //S存放A+B的闵可夫斯基和
int tot;
inline void Minkovski(){                                                            //闵可夫斯基和
    for(int i=1;i<n;i++)    a[i] = A[i + 1] - A[i];
    a[n] = A[1] - A[n];
    for(int i=1;i<m;i++)    b[i] = B[i + 1] - B[i];
    b[m] = B[1] - B[m];                                                             //将两个凸包上的边向量都存入a,b中

    S[++tot] = A[1] + B[1];                                                         //以A1+B1为起始点
    int p1 = 1,p2 = 1;
    while(p1 <= n && p2 <= m)   tot++,S[tot] = S[tot - 1] + (a[p1] * b[p2] >= 0 ? a[p1++] : b[p2++]);  //由于向量具有可加性,所以直接加上凸的那个边向量即可
    while(p1 <= n)  tot++,S[tot] = S[tot - 1] + a[p1++];
    while(p2 <= m)  tot++,S[tot] = S[tot - 1] + b[p2++];                            //将剩余的加进去
}

需要注意的是，这样求出来的 Minkovski 可能存在三点共线的情况，所以要对求出来的 S 再求一遍凸包。

这样才能避免三点共线的问题。

二. 具体应用

[JSOI2018] 战争

闵可夫斯基板子题。

题目说白了就是求两个凸包是否相交。

那么我们只需要求出两个凸包的最短距离是否小于等于 0 即可。

而两个凸包间的最短距离实际上就是原点到这两个凸包之差的 Minkovski 的最短距离。

也即求出 \mathcal{A} 与 \mathcal{-B} 的 Minkovski。

至于多组询问的 d，实际上就是判断点 d 是否在 Minkovski 内。

求一个点是否在一个凸包内的方法：

三角剖分，二分查找。

如下图：

要求 F 是否在凸包内。

先二分出第一个极角小于 F 的点（图中为 E）。

然后再比较 \overrightarrow{EF} 和 \overrightarrow{EA} 的外积（叉乘）是否小于等于 0 即可。

注意要特判边界情况。

当共线时比较长度。

为了方便写代码，实现时可以将第一个点移动至原点处，其余所有点跟着平移即可。

code

纳西妲和兰纳罗

我自己出的一道题，是 Minkovski 的变式，当作练习题就不讲了。

三. 其他应用