题意
旋转卡壳。
先找第一个凸包上纵坐标最小的点\(p\)和第二个凸包上纵坐标最大的点\(q\),之后旋转卡壳,求两条线段之间的最短距离。
code:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=10010;
const double eps=1e-10;
const double inf=0x3f3f3f3f;
int n,m;
struct Point
{
double x,y;
inline double len(){return sqrt(x*x+y*y);}
Point operator+(const Point a)const
{
Point res;
res.x=x+a.x,res.y=y+a.y;
return res;
}
Point operator-(const Point a)const
{
Point res;
res.x=x-a.x,res.y=y-a.y;
return res;
}
Point operator*(double k)const
{
Point res;
res.x=x*k,res.y=y*k;
return res;
}
Point operator/(double k)const
{
Point res;
res.x=x/k,res.y=y/k;
return res;
}
double operator*(const Point a)const{return x*a.y-y*a.x;}
double operator&(const Point a)const{return x*a.x+y*a.y;}
};
Point st;
Point p1[maxn],p2[maxn];
inline int dcmp(double x)
{
if(fabs(x)<=eps)return 0;
return x<0?-1:1;
}
inline Point get(Point a,Point b){return b-a;}
inline double dis1(Point a,Point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double dis2(Point a,Point b,Point c)//a->bc
{
if(!dcmp(get(b,c).len()))return dis1(a,b);
if(dcmp(get(b,a)&get(b,c))<0)return dis1(a,b);
if(dcmp(get(c,a)&get(c,b))<0)return dis1(a,c);
return fabs((get(a,b)*get(a,c))/dis1(b,c));
}
inline double dis3(Point a,Point b,Point c,Point d)
{
return min(min(dis2(a,c,d),dis2(b,c,d)),min(dis2(c,a,b),dis2(d,a,b)));
}
inline double solve(Point* p1,Point* p2,int n,int m)
{
int p=0,q=0;
for(int i=0;i<n;i++)if(p1[i].y<p1[p].y)p=i;
for(int i=0;i<m;i++)if(p2[i].y>p2[q].y)q=i;
p1[n]=p1[0];p2[m]=p2[0];
double res=inf;
for(int i=0;i<n;i++)
{
while(dcmp(get(p1[p],p1[p+1])*get(p2[q],p2[q+1]))>0)q=(q+1)%m;
res=min(res,dis3(p1[p],p1[p+1],p2[q],p2[q+1]));
p=(p+1)%n;
}
return res;
}
int main()
{
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
while(~scanf("%d%d",&n,&m)&&n&&m)
{
for(int i=0;i<n;i++)scanf("%lf%lf",&p1[i].x,&p1[i].y);
for(int i=0;i<m;i++)scanf("%lf%lf",&p2[i].x,&p2[i].y);
for(int i=0;i<n-2;i++)
if(dcmp(get(p1[i],p1[i+1])*get(p1[i+1],p1[i+2]))<0){reverse(p1,p1+n);break;}
else if(dcmp(get(p1[i],p1[i+1])*get(p1[i+1],p1[i+2]))>0)break;
for(int i=0;i<m-2;i++)
if(dcmp(get(p2[i],p2[i+1])*get(p2[i+1],p2[i+2]))<0){reverse(p2,p2+m);break;}
else if(dcmp(get(p2[i],p2[i+1])*get(p2[i+1],p2[i+2]))>0)break;
printf("%.5lf\n",solve(p1,p2,n,m));
}
return 0;
}