题目:计算两个不相交凸多边形间的最小距离。
分析:计算几何、凸包、旋转卡壳。分别求出凸包,利用旋转卡壳求出对踵点对,枚举距离即可。
注意:1.利用向量法判断旋转,而不是计算角度;避免精度问题和TLE。
2.遇到平行线段时,需要计算4组点到线段距离,不然会漏掉对踵点对。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cmath> using namespace std; //点结构
typedef struct pnode
{
double x,y,d;
pnode( double a, double b ) {x = a;y = b;}
pnode(){};
}point;
point T,P[10005],Q[10005]; //线段结构
typedef struct lnode
{
double x,y,dx,dy;
lnode( point a, point b ) {x = a.x;y = a.y;dx = b.x-a.x;dy = b.y-a.y;}
lnode(){};
}line; //叉乘 ab*ac
double crossproduct( point a, point b, point c )
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
} //两点间距离
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 dist( point a, point p, point q )
{
line l = line( p, q );
//判断垂足位置
if ( (l.dx*(p.x-a.x)+l.dy*(p.y-a.y))*(l.dx*(q.x-a.x)+l.dy*(q.y-a.y)) < 0 )
return fabs(l.dx*(a.y-l.y)-l.dy*(a.x-l.x))/sqrt(l.dx*l.dx+l.dy*l.dy);
else return min( dist( a, p ), dist( a, q ) );
} //坐标比较
bool cmp1( point a, point b )
{
return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
} //级角比较
bool cmp2( point a, point b )
{
double cp = crossproduct( T, a, b );
if ( !cp ) return a.d < b.d;
else return cp > 0;
} //凸包
int graham( point* p, int n )
{
sort( p+0, p+n, cmp1 );
for ( int i = 1 ; i < n ; ++ i )
p[i].d = dist( p[0], p[i] );
T = p[0];
sort( p+1, p+n, cmp2 ); int top = 1;
for ( int i = 2 ; i < n ; ++ i ) {
while ( top > 0 && crossproduct( p[top-1], p[top], p[i] ) <= 0 ) -- top;
p[++ top] = p[i];
}
p[++ top] = p[0]; return top;
} //利用向量判断夹角
double judge( point a, point b, point c, point d )
{
return crossproduct( c, d, point( c.x+b.x-a.x, c.y+b.y-a.y ) );
} //旋转卡壳
double rotatingcalipers( point* p, point* q, int n, int m )
{
double D = 30000.0;
int R = 0;
for ( int i = 0 ; i < m ; ++ i )
if ( q[i].x >= q[R].x ) R = i;
for ( int L = 0 ; L < n ; ++ L ) {
while ( judge( p[L], p[L+1], q[R], q[R+1] ) < 1e-6 )
R = (R+1)%m;
//两条边平行时,需计算平行线段间最短距离,即四个点到线段的距离
D = min( min( D, dist( p[L], q[R] ) ),
min( min( dist( p[L], q[R], q[R+1] ), dist( q[R], p[L], p[L+1] ) ),
min( dist( p[L+1], q[R], q[R+1] ), dist( q[R+1], p[L], p[L+1] ) ) ) );
} return D;
} int main()
{
int N,M;
while ( scanf("%d%d",&N,&M) && N ) {
for ( int i = 0 ; i < N ; ++ i )
scanf("%lf%lf",&P[i].x,&P[i].y);
for ( int i = 0 ; i < M ; ++ i )
scanf("%lf%lf",&Q[i].x,&Q[i].y); N = graham( P, N );
M = graham( Q, M ); printf("%.5lf\n",rotatingcalipers( P, Q, N, M ));
}
return 0;
}