题目链接 问题分析 题意即求两个凸包间的最小距离。 一开始十分暴力地写了一个闵可夫斯基和，后来发现变种的旋转卡壳转一转就好了QAQ 闵可夫斯基和的思路十分简单，下面看一下旋转卡壳的做法： 不难发现两个凸包间的最短距离一定像上图那样。所以我们只需要枚举一个凸包的边，找另一个凸包上的对踵点就好了。这个过程需要执行两次。 注意判断线段平行和求点到线段距离的细节。 参考程序 闵可夫斯基和版： #inc

这题真神了，同样的代码用G++就WA用C++就AC…… 题意是说，给两个凸多边形，求它们边界之间距离的最小值。做法类似于求凸包的旋转卡壳法，先取一个凸包的最高点和另一个凸包的最低点，画出方向相反的两条射线。然后同时逆时针旋转两条射线至其中一条与对应多边形的一条边相交，然后继续更新射线旋转。因为可以证明说最短距离是点到线的距离，所以不断更新就好了…… #include<stdio.h>#i