CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

======闵可夫斯基和======
(这里的闵可夫斯基和只针对凸多边形)
=====定义=====
  * 两个欧几里得空间里点集的和，又称作两个空间的膨胀集，即：$A+B=\{a+b|a\in A,b\in B\}$
  * 其实可以把$B$看作一个向量集，把$A$每个点沿着$B$中每一个向量进行一波平移。
{{:2020-2021:teams:farmer_john:bazoka13:o_闵可夫斯基和1.png?400|}}（图中粉色边框即为$A$和$B$的闵可夫斯基和）
=====性质=====
  * 满足加法交换律：$A+B=B+A$
  * 两个凸包的闵可夫斯基和由两个凸包的边构成。<del>过菜不会证明</del>
=====求法=====
  * 根据性质二，只需要把边集取出来直接极角排序
  * 之后分别找到边界点绕着跑一圈即可定位
=====例题=====
  * [[https://www.luogu.com.cn/problem/P4557|[JSOI2018]战争]]
    * 题意：将一个点集根据一个向量进行平移，判断是否会与另一个点集冲突，当两者的凸包出现重叠时发生冲突 
    * 题解：直接将待平移的点集取反，然后求两个点集的闵可夫斯基和，判断平移的向量坐标是否位于期中即可
  * [[http://acm.hdu.edu.cn/showproblem.php?pid=4785|HDU 4785 Exhausted Robot]]
    * 题意：矩形房间，一个扫地机器人和一些家具，均为凸多边形，求机器人能扫到的面积
    * 题解：和上一道思路差不多，求出来闵可夫斯基和之后直接扫描线

CVBB ACM Team

用户工具

站点工具

页面工具