【旋转卡壳】poj3608 Bridge Across Islands

给你俩凸包，问你它们的最短距离。

咋做就不讲了，经典题，网上一片题解。

把凸包上的点逆时针排序。可以取它们的平均点，然后作极角排序。

旋转卡壳其实是个很模板化的东西……

先初始化分别在凸包P和Q上取哪个点，一般在P上取纵坐标最小的点，在Q上取纵坐标最大的点

for i=1 to n（n是凸包P上的点数）

{

while(两条边的叉积>0)

{

　　凸包Q上的点++

}

计算当前两条边之间的答案（或者说每条边的2个端点到另一条边的答案）

凸包P上的点++

}

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define EPS 0.0000000001

struct Point

{

	double x,y;

	Point(){}

	Point(const double &X,const double &Y)

	  {

	  	x=X;

	  	y=Y;

	  }

	double Length()

	  {

	  	return sqrt(x*x+y*y);

	  }

}p[2][10010],bao[2][10010],ave;

typedef Point Vector;

Vector operator - (const Point &a,const Point &b)

{

	return Vector(a.x-b.x,a.y-b.y);

}

bool cmp (const Point &a,const Point &b)

{

	return atan2((a-ave).y,(a-ave).x)<atan2((b-ave).y,(b-ave).x);

}

double Cross(const Vector &a,const Vector &b)

{

	return a.x*b.y-a.y*b.x;

}

double Dot(const Vector &a,const Vector &b)

{

	return a.x*b.x+a.y*b.y;

}

double calc(Point P,Point A,Point B)

{

	Vector v1=B-A,v2=P-A,v3=P-B;

	if(Dot(v1,v2)<EPS) return v2.Length();

	else if(Dot(v1,v3)>(-EPS)) return v3.Length();

	else return fabs(Cross(v1,v2))/v1.Length();

}

int n,m;

int main()

{

	//freopen("y.in","r",stdin);

	while(1)

	  {

	  	scanf("%d%d",&n,&m);

	  	if(n==0 && m==0)

	  	  break;

	  	for(int i=0;i<n;++i)

	  	  {

	  	  	scanf("%lf%lf",&p[0][i].x,&p[0][i].y);

	  	  	ave.x+=p[0][i].x;

	  	  	ave.y+=p[0][i].y;

	  	  }

	  	ave.x/=(double)n;

	  	ave.y/=(double)n;

	  	for(int i=0;i<m;++i)

	  	  scanf("%lf%lf",&p[1][i].x,&p[1][i].y);

		sort(p[0],p[0]+n,cmp);

		ave.x=ave.y=0;

		for(int i=0;i<m;++i)

		  {

		  	ave.x+=p[1][i].x;

	  	  	ave.y+=p[1][i].y;

		  }

	  	ave.x/=(double)m;

	  	ave.y/=(double)m;

		sort(p[1],p[1]+m,cmp);

	  	int nowP=0,nowQ=0;

	  	for(int i=1;i<n;++i)

	  	  if(p[0][i].y-p[0][nowP].y<(-EPS))

	  	    nowP=i;

	  	for(int i=1;i<m;++i)

	  	  if(p[1][i].y-p[1][nowQ].y>EPS)

	  	    nowQ=i;

	  	double ans=1000000000000000007.0;

	  	for(int i=0;i<n;++i)

		  {

			while(Cross(p[1][(nowQ+1)%m]-p[1][nowQ],p[0][nowP]-p[0][(nowP+1)%n])>EPS)

			  nowQ=(nowQ+1)%m;

			ans=min(ans,

			min(calc(p[0][nowP],p[1][nowQ],p[1][(nowQ+1)%m]),

			min(calc(p[0][(nowP+1)%n],p[1][nowQ],p[1][(nowQ+1)%m]),

			min(calc(p[1][nowQ],p[0][nowP],p[0][(nowP+1)%n]),

			calc(p[1][(nowQ+1)%m],p[0][nowP],p[0][(nowP+1)%n])))));

			nowP=(nowP+1)%n;

		  }

		printf("%.5lf\n",ans);

	  }

	return 0;

}

巴特西

【旋转卡壳】poj3608 Bridge Across Islands

最新文章

热门文章