题目链接：http://poj.org/problem?id=3608
表示旋转卡壳这个算法看起来比较好懂（虽然证明起来还是有一点难度的，但是只观的看还是比较好理解的）但是代码实现起来还是不怎么好理解的
关键在计算几何这里面要求尽量不涉及到角度的计算，基本上都是点积和差积，因为这样能避免调用系统的三角函数，所以能最大限度的减少精度
损失
这个题目可以用枚举方法，可以用凸包的单调性来剪枝，但是还是容易超时
但是旋转卡壳算法O（n）的复杂度，应该来说在渐进时间复杂度的意义上是最优的算法了
首先选取p的最低点，和q的最高点，完成之后就开始卡壳，卡壳的时候还是利用面积
while((rec=cross(q[pos_q],p[pos_p+1],p[pos_p])-cross(q[pos_q+1],p[pos_p+1],p[pos_p])) > eps)
{
pos_q=(pos_q+1)%m;
}
if(rec < -eps)
ans=MIN(ans,point_to_seg(p[pos_p],p[pos_p+1],q[pos_q]));
else
ans=MIN(ans,seg_to_seg(p[pos_p],p[pos_p+1],q[pos_q],q[pos_q+1]));
pos_p=(pos_p+1)%n;
如果这次的面积比下一次的大，那么说明再往下走有可能更小，也就是还没找到最近的点，接着向下
不过还有一个条件，那么就是如果两次面积差接近0，那么说明两次的面积没有什么变化，这个最短
距离就是ans和两条线段之间的最短距离了，如果两次距离差不是0，那么就是点到线段之间的距离了
这个还是比较好理解的，然后一次做完之后p就到下一个点开始做，可能有人认为这个算法是一个平方
算法，其实还是线性的，因为里面的循环只是在第一次的时候可能会转半圈，后来就几乎是常数了！
至于最后结果为什么要两边都枚举一遍，一个取最低点，一个取最高点，然后反过来一下！
旋转卡壳算法还没怎么理解，还要好好学习！
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf 1e8
#define eps 1e-8
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
struct point
{
double x;
double y;
}p[11000],q[11000];
struct line
{
point a;
point b;
};
double cross(point &a,point &b,point &c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double dis(point &a,point &b)
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int cmp_p(const void *a,const void *b)
{
return cross(p[0],*(point*)a,*(point*)b) > 0 ? -1 : 1;
}
int cmp_q(const void *a,const void *b)
{
return cross(q[0],*(point*)a,*(point*)b) > 0 ? -1 : 1;
}
double dot(point a,point b)
{
return a.x*b.x+a.y*b.y;
}
double point_to_seg(point a,point b,point c)//c 到直线a-b的距离
{
point ab,ac;
ab.x=b.x-a.x;
ab.y=b.y-a.y;
ac.x=c.x-a.x;
ac.y=c.y-a.y;
double f=dot(ab,ac);
if(f<0)return dis(a,c);
double f1=dot(ab,ab);
if(f>f1)return dis(b,c);
f=f/f1;
point d;
d.x=a.x+ab.x*f;
d.y=a.y+ab.y*f;
return dis(d,c);
}
double seg_to_seg(point a1,point b1,point a2,point b2)
{
return min(min(point_to_seg(a1,b1,a2),point_to_seg(a1,b1,b2)),min(point_to_seg(a2,b2,a1),point_to_seg(a2,b2,b1)));
}
int n,m;
double find_ans(point *p,int n,point *q,int m)
{
int i,j,k,pos_p,pos_q;
double ans=inf,rec;
p[n]=p[0];
q[m]=q[0];
pos_p=pos_q=0;
for(i=1;i<n;i++)
if(p[i].y < p[pos_p].y)
pos_p=i;
for(i=1;i<m;i++)
if(q[i].y > q[pos_q].y)
pos_q=i;
for(i=0;i<n;i++)
{
while((rec=cross(q[pos_q],p[pos_p+1],p[pos_p])-cross(q[pos_q+1],p[pos_p+1],p[pos_p])) > eps)
{
pos_q=(pos_q+1)%m;
}
if(rec < -eps)
ans=MIN(ans,point_to_seg(p[pos_p],p[pos_p+1],q[pos_q]));
else
ans=MIN(ans,seg_to_seg(p[pos_p],p[pos_p+1],q[pos_q],q[pos_q+1]));
pos_p=(pos_p+1)%n;
}
return ans;
}
int main()
{
int i,j,k,pos;
point temp,temp1;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0 && m==0)
return 0;
temp.y=1e8;
for(i=0;i<n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i].y < temp.y)
temp=p[i],pos=i;
}
p[pos]=p[0],p[0]=temp;
temp.y=1e8;
for(i=0;i<m;i++)
{
scanf("%lf%lf",&q[i].x,&q[i].y);
if(q[i].y < temp.y)
temp=q[i],pos=i;
}
q[pos]=q[0],q[0]=temp;
qsort(p,n,sizeof(p[0]),cmp_p);
qsort(q,m,sizeof(q[0]),cmp_q);
printf("%.5lf\n",sqrt(MIN(find_ans(p,n,q,m),find_ans(q,m,p,n))));
}
return 0;
}