poj 3608 Bridge Across Islands

题目：计算两个不相交凸多边形间的最小距离。

分析：计算几何、凸包、旋转卡壳。分别求出凸包，利用旋转卡壳求出对踵点对，枚举距离即可。

注意：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;

}

巴特西

poj 3608 Bridge Across Islands

最新文章

热门文章