旋转卡壳+两个凸包最近距离

两个凸包的最近距离

当模板用 用旋转写

#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define eps 1e-8
#define inf 0x3f3f3f3f
using namespace std;
struct {
	double x,y;
}A[10010],B[10010];
double MIN(double a,double b){
	return a<b?a:b;
}
double dist(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double dotp(point p0,point p1,point p2){//点积
	return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
double cp(point p0,point p1,point p2){//叉积
	return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double pld(point p1,point p2,point p3){//点线距
	if(dist(p1,p2)<eps)return dist(p2,p3);
	if(dotp(p1,p2,p3)+eps<0)return dist(p1,p3);
	if(dotp(p2,p1,p3)+eps<0)return dist(p2,p3);
	return fabs(cp(p1,p2,p3)/dist(p1,p2));
}
double lld(point p1,point p2,point p3,point p4){//线线距
	return MIN(MIN(pld(p1,p2,p3),pld(p1,p2,p4)),MIN(pld(p3,p4,p1),pld(p3,p4,p2)));
}
double rotating_calipers(point *p,point *q,int n,int m){//旋转卡壳 两个凸包的
	int i,d=0,u=0;
	p[n]=p[0];q[m]=q[0];
	for(int i=0;i<n;++i){
		if(p[i].y<p[d].y)d=i;//y值最小点
	}
	for(int i=0;i<m;++i){//y值最大点
		if(q[i].y>q[u].y)u=i;
	}
	double ans=inf;
	for(i=0;i<n;++i){
		double cnt;
		while(cnt=cp(p[d+1],q[u+1],p[d])-cp(p[d+1],q[u],p[d])>eps)u=(u+1)%m;
		if(cnt+eps<0)ans=MIN(ans,pld(p[d],p[d+1],q[u]));
		else ans=MIN(ans,lld(p[d],p[d+1],q[u],q[u+1]));
		d=(d+1)%n;
	}
	return ans;
}
int main()
{
	int i,n,m;
	while(scanf("%d%d",&n,&m),n||m){
		for(i=0;i<n;++i){
			scanf("%lf%lf",&A[i].x,&A[i].y);
		}
		for(i=0;i<m;++i){
			scanf("%lf%lf",&B[i].x,&B[i].y);
		}
		printf("%.5lfn",MIN(rotating_calipers(A,B,n,m),rotating_calipers(B,A,m,n)));//两个方向都求一下
	}
	return 0;
}