Bridge Across Islands
Description
Thousands of thousands years ago there was a small kingdom located in the middle of the Pacific Ocean. The territory of the kingdom consists two separated islands. Due to the impact of the ocean current, the shapes of both the islands became convex polygons. The king of the kingdom wanted to establish a bridge to connect the two islands. To minimize the cost, the king asked you, the bishop, to find the minimal distance between the boundaries of the two islands.
Input
The input consists of several test cases. Each test case begins with two integers N, M. (3 ≤ N, M ≤ 10000) Each of the next N lines contains a pair of coordinates, which describes the position of a vertex in one convex polygon. Each of the next M lines contains a pair of coordinates, which describes the position of a vertex in the other convex polygon. A line with N = M = 0 indicates the end of input. The coordinates are within the range [-10000, 10000].
Output
For each test case output the minimal distance. An error within 0.001 is acceptable.
Sample Input
4 4
0.00000 0.00000
0.00000 1.00000
1.00000 1.00000
1.00000 0.00000
2.00000 0.00000
2.00000 1.00000
3.00000 1.00000
3.00000 0.00000
0 0
Sample Output
1.00000
题意理解：
给定两个分离的凸包s，t的点，但是这些点并没有按一定的顺序组成凸包，所以首先要求凸包。然后用旋转卡壳，旋转2*pi的角度即可。
#include<algorithm> #include<iostream> #include<stdio.h> #include<cstdlib> #include<math.h> using namespace std; const double esp=1.0e-6; const double oo=1e200; const double pi=acos(-1.0); struct point { double x,y; point operator - (const point & r)const { point tmp; tmp.x=x-r.x; tmp.y=y-r.y; return tmp; } }; point *s,*t; int dblcmp(double x) { if(fabs(x)<esp) return 0; return (x>0)?1:-1; } double distances(point a,point b) { return sqrt( (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y) ); } double crossleft(point a,point b,point c) { return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); } double dot(point a,point b,point c) { return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y); } double dis_p_l(point a,point b,point c) {//点a，到线段bc的距离 if( dblcmp( dot(b,c,a) )>=0&&dblcmp( dot(c,b,a) )>=0) return fabs(crossleft(a,b,c))/distances(b,c); else return min(distances(a,b),distances(a,c)); } double dis_l_l(point a1,point a2,point b1,point b2) {//计算平行线段a1a2，b1b2，直接的最短距离 double k1,k2,k3,k4,k; k1=dis_p_l(a1,b1,b2); k2=dis_p_l(a2,b1,b2); k3=dis_p_l(b1,a1,a2); k4=dis_p_l(b2,a1,a2); k=min(k1,k2); if(k>min(k3,k4)) k=min(k3,k4); return k; } double atan(point a) {//求非零向量a的倾斜角 [0,2*pie） if(fabs(a.x)<esp) return (a.y>0)?(pi/2):(3*pi/2); if(a.x<0) return atan(a.y/a.x)+pi; if(a.y>=0) return atan(a.y/a.x); else return 2*pi+atan(a.y/a.x); } double rotating_calipers(int n,int m) { int tt,ss; s[n]=s[0]; t[m]=t[0]; tt=ss=0; for(int i=0;i<n;i++) if( s[ss].y<s[i].y||(s[ss].y==s[i].y&&s[ss].x<s[i].x) ) ss=i; for(int i=0;i<m;i++) if( t[tt].y>t[i].y||(t[tt].y==t[i].y&&t[tt].x>t[i].x) ) tt=i; double f1,f2,angle1,angle2,d,ans=oo; angle1=pi; angle2=0; f1=angle1; f2=angle2; while(angle1<=3*pi&&angle2<=2*pi) { point tmps,tmpt; tmps=s[ss+1]-s[ss]; tmpt=t[tt+1]-t[tt]; angle1=atan(tmps); angle2=atan(tmpt); while(angle1<f1) angle1+=2*pi; while(angle2<f2) angle2+=2*pi; f1=angle1; f2=angle2; double k=angle1-angle2-pi; if(dblcmp(k)==0) { d=dis_l_l(s[ss],s[ss+1],t[tt],t[tt+1]); ss=(ss+1)%n; tt=(tt+1)%m; } else if(dblcmp(k)<0) { d=dis_p_l(t[tt],s[ss],s[ss+1]); ss=(ss+1)%n; } else { d=dis_p_l(s[ss],t[tt],t[tt+1]); tt=(tt+1)%m; } if(ans>d) ans=d; } return ans; } int Jarvis(point *p,int n) { point *tmp=new point[n+3]; int k,top=0; tmp[top++]=p[0]; tmp[top++]=p[1]; for(int i=2;i<n;i++) { while(top>1&&dblcmp( crossleft(tmp[top-2],tmp[top-1],p[i]) )<=0) top--; tmp[top++]=p[i]; } k=top; tmp[top++]=p[n-2]; for(int i=n-3;i>=0;i--) { while(top>k&&dblcmp( crossleft(tmp[top-2],tmp[top-1],p[i]) )<=0) top--; tmp[top++]=p[i]; } for(int i=0;i<top-1;i++) p[i]=tmp[i]; delete [] tmp; return top-1; } int main() { // freopen("1.txt","r",stdin); int n,m; while(scanf("%d %d",&n,&m)!=EOF) { s=new point[n+1]; t=new point[m+1]; if(n==0&&m==0) break; for(int i=0;i<n;i++) scanf("%lf%lf",&s[i].x,&s[i].y); for(int i=0;i<m;i++) scanf("%lf%lf",&t[i].x,&t[i].y); n=Jarvis(s,n); m=Jarvis(t,m); double ans=rotating_calipers(n,m); printf("%.5lf/n",ans); delete [] s; delete [] t; } return 0; }
