首页 > 代码库 > poj 3608 Bridge Across Islands 两凸包间最近距离
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\n",ans); 133 } 134 return 0; 135 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。