闵可夫斯基和 | Kyons'Blog 




 
 
 
 



 
 



闵可夫斯基和

定义

什么是闵可夫斯基和?
两个凸包$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)$
图呢,长这样:
1.png

流程

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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\}$
我们称其为闵可夫斯基差
当然,取反这个骚操作,还是更好用


 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载