题目链接:https://vjudge.net/problem/POJ-3608
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 #define eps 1e-10 7 const int N = 1e4+9; 8 int n,m; 9 struct Point{ 10 double x,y; 11 Point operator - (const Point& b)const{ 12 return (Point){x-b.x,y-b.y}; 13 } 14 double operator ^ (const Point& b)const{ 15 return x*b.y-b.x*y; 16 } 17 double operator * (const Point& b)const{ 18 return x*b.x + y*b.y; 19 } 20 }pN[N],pM[N],p0; 21 bool cmp(Point a,Point b){ 22 if(atan2(a.y-p0.y,a.x-p0.x) != atan2(b.y-p0.y,b.x-p0.x)){ 23 return atan2(a.y-p0.y,a.x-p0.x) < atan2(b.y-p0.y,b.x-p0.x); 24 } 25 return a.x < b.x; 26 } 27 double dis(Point a,Point b){ 28 return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); 29 } 30 //点到线段最短距离 31 inline double point_to_seg(Point a,Point s,Point t){ 32 if(dis(s,t) < eps) return dis(a,s); 33 if( ((t-s)*(a-s)) < -eps) return dis(a,s); 34 if( ((s-t)*(a-t)) < -eps) return dis(a,t); 35 return fabs( ((t-s)^(a-s)) / dis(s,t) ); 36 } 37 inline double seg_to_seg(Point A, Point B, Point C, Point D){ 38 return min(min(point_to_seg(C,A,B), point_to_seg(D,A, B)), min(point_to_seg(A,C, D), point_to_seg(B,C, D))); 39 } 40 inline void init(){ 41 int k; 42 scanf("%lf %lf",&pN[0].x,&pN[0].y); 43 p0 = pN[0]; 44 for(int i = 1;i<n;++i){ 45 scanf("%lf %lf",&pN[i].x,&pN[i].y); 46 if(p0.y>pN[i].y || (p0.y==pN[i].y && p0.x>pN[i].x)){ 47 p0 = pN[i]; 48 k = i; 49 } 50 } 51 pN[k] = pN[0]; 52 pN[0] = p0; 53 sort(pN+1,pN+n,cmp); 54 55 56 scanf("%lf %lf",&pM[0].x,&pM[0].y); 57 p0 = pM[0]; 58 for(int i = 1;i<m;++i){ 59 scanf("%lf %lf",&pM[i].x,&pM[i].y); 60 if(p0.y>pM[i].y || (p0.y==pM[i].y && p0.x>pM[i].x)){ 61 p0 = pM[i]; 62 k = i; 63 } 64 } 65 pM[k] = pM[0]; 66 pM[0] = p0; 67 sort(pM+1,pM+m,cmp); 68 } 69 inline void solve(){ 70 int yminN = 0,ymaxM = 0; 71 for(int i = 1;i<n;++i) if(pN[i].y < pN[yminN].y) yminN = i; 72 for(int i = 1;i<m;++i) if(pM[i].y > pM[ymaxM].y) ymaxM = i; 73 pN[n] = pN[0]; 74 pM[m] = pM[0]; 75 double tem,ans = 0x3f3f3f3f; 76 for(int i = 0;i<n;++i){ 77 while(tem = ( (pM[ymaxM+1]-pN[yminN+1])^(pN[yminN]-pN[yminN+1]) ) - ( (pM[ymaxM] - pN[yminN+1])^(pN[yminN]-pN[yminN+1])) > eps){ 78 ymaxM++; 79 if(ymaxM == m) ymaxM = 0; 80 } 81 ans = min(ans,seg_to_seg(pN[yminN],pN[yminN+1],pM[ymaxM],pM[ymaxM+1])); 82 yminN++; 83 if(yminN == n) yminN = 0; 84 } 85 printf("%.5f\n",ans); 86 } 87 int main(){ 88 while(~scanf("%d %d",&n,&m) && (n+m) ){ 89 init(); 90 solve(); 91 } 92 return 0; 93 }View Code