poj 3608 Bridge Across Islands 两凸包间最近距离

  1 /**
  2 旋转卡壳，，
  3 **/
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <cstdio>
  8 using namespace std;
  9 
 10 const double eps = 1e-8;
 11 struct point {
 12     double x,y;
 13     point(double x=0,double y =0):x(x),y(y){}
 14 };
 15 
 16 int dcmp(double x){
 17     if(fabs(x)<eps)
 18         return 0;
 19     else
 20         return x<0?-1:1;
 21 }
 22 
 23 point p[10020],p1[10020];
 24 point q[10020],q1[10020];
 25 int maxid,minid;
 26 int N,M;
 27 typedef point Vector;
 28 
 29 Vector operator -(point a,point b){
 30     return Vector(a.x-b.x,a.y-b.y);
 31 }
 32 
 33 double cross(Vector a,Vector b){
 34     return a.x*b.y-a.y*b.x;
 35 }
 36 
 37 double dot(Vector a,Vector b){
 38     return a.x*b.x+a.y*b.y;
 39 }
 40 bool  cmp(point a,point b){
 41     if(a.x==b.x)
 42         return a.y<b.y;
 43     return a.x<b.x;
 44 }
 45 
 46 bool operator ==(const point &a,const point &b){
 47     return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
 48 }
 49 
 50 double length(Vector a){
 51     return sqrt(a.x*a.x+a.y*a.y);
 52 }
 53 
 54 int convexHull(point *p,int n,point *ch){
 55     sort(p,p+n,cmp);
 56     int m =0;
 57     for(int i=0;i<n;i++){
 58         while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)
 59             m--;
 60         ch[m++] = p[i];
 61     }
 62     int k =m;
 63     for(int i = n-2;i>=0;i--){
 64         while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)
 65             m--;
 66         ch[m++] = p[i];
 67     }
 68     if(n>1) m--;
 69     return m;
 70 }
 71 
 72 double distanceToSegment(point p,point a,point b){
 73     if(a==b)
 74         return length(p-a);
 75     Vector v1 = b-a,v2 = p-a, v3 = p-b;
 76     if(dcmp(dot(v1,v2))<0)
 77         return length(v2);
 78     else if(dcmp(dot(v1,v3))>0)
 79         return length(v3);
 80     else
 81         return fabs(cross(v1,v2))/length(v1);
 82 }
 83 
 84 double distanceBetweenSegment(point a,point b,point c,point d){
 85     return min(min(distanceToSegment(a,c,d),distanceToSegment(b,c,d)),min(distanceToSegment(c,a,b),distanceToSegment(d,a,b)));
 86 }
 87 
 88 void getMaxAndMin(int &maxid,int &minid){
 89     maxid =0;
 90     minid =0;
 91     for(int i=1;i<N;i++){
 92         if(p1[i].y<p1[minid].y)
 93             minid =i;
 94     }
 95     for(int i=0;i<M;i++){
 96         if(q1[i].y>q1[maxid].y)
 97             maxid = i;
 98     }
 99 }
100 
101 double solve(point *p,point *q,int minid,int maxid,int N,int M){
102     double temp,ret = 1e5;
103     p[N] = p[0];
104     q[M] = q[0];
105     for(int i=0;i<N;i++){
106         while(temp = dcmp(cross(q[maxid]-q[maxid+1],p[minid+1]-p[minid]))>0){
107             maxid = (maxid+1)%M;
108         }
109         if(temp<0)
110             ret = min(ret,distanceToSegment(q[maxid],p[minid],p[minid+1]));
111         else
112             ret = min(ret,distanceBetweenSegment(p[minid],p[minid+1],q[maxid],q[maxid+1]));
113         minid = (minid+1)%N;
114     }
115     return ret;
116 }
117 
118 int main()
119 {
120 
121     while(cin>>N>>M){
122         if(N==0&&M==0)
123             break;
124         for(int i=0;i<N;i++)
125             cin>>p[i].x>>p[i].y;
126         for(int i=0;i<M;i++)
127             cin>>q[i].x>>q[i].y;
128         N = convexHull(p,N,p1);
129         M = convexHull(q,M,q1);
130         getMaxAndMin(maxid,minid);
131         double ans = solve(p1,q1,minid,maxid,N,M);
132         printf("%.5lf
",ans);
133     }
134     return 0;
135 }