继续上一次的旋转卡壳的问题,这次是求两个凸包的最短距离,
其实选择卡壳就是只要找到"当前向量面积不小于下一个向量面积"即可,
满足这个条件,当前的两个ymin和ymax点就是一对对踵点了。
代码如下,欢迎参考:
#include<cmath>
#include<cstdio>
#include<iostream>
using namespace std;
typedef struct{float x,y;} Dot;
Dot operator -(Dot a,Dot b){Dot c={a.x-b.x,a.y-b.y};return c;}
float operator *(Dot a,Dot b){return a.x*b.y-b.x*a.y;}
float operator /(Dot a,Dot b){return a.x*b.x+a.y*b.y;......
阅读全文