poj 3608 Bridge Across Islands(两凸包最近距离)
很裸的题，还是用旋转卡壳的方法。输入点的顺序就是逆时针输入了。
#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<fstream>#include<sstream>#include<vector>#include<string>#include<cstdio>#include<bitset>#include<stack>#include<queue>#include<cmath>#include<map>#include<set>#define FF(i, a, b) for(int i=a; i<b; i++)#define FD(i, a, b) for(int i=a; i>=b; i--)#define REP(i, n) for(int i=0; i<n; i++)#define CLR(a, b) memset(a, b, sizeof(a))#define PB push_back#define LL long long#define eps 1e-10#define debug puts("**debug**")using namespace std;struct Point{ double x, y; Point(double x=0, double y=0):x(x), y(y){}};typedef Point Vector;Vector operator + (Vector a, Vector b) { return Vector(a.x+b.x, a.y+b.y); }Vector operator - (Vector a, Vector b) { return Vector(a.x-b.x, a.y-b.y); }Vector operator * (Vector a, double p) { return Vector(a.x*p, a.y*p); }Vector operator / (Vector a, double p) { return Vector(a.x/p, a.y/p); }bool operator < (const Point& a, const Point& b){ return a.x < b.x || (a.x == b.x && a.y <b.y);}int dcmp(double x){ if(fabs(x) < eps) return 0; return x < 0 ? -1 : 1;}bool operator == (const Point& a, const Point& b){ return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;}double Dot(Vector a, Vector b) { return a.x*b.x + a.y*b.y; }double Length(Vector a) { return sqrt(Dot(a, a)); }double Cross(Vector a, Vector b) { return a.x*b.y - a.y*b.x; }//如果输入点是顺时针输入，转为逆时针顺序void anticolockwise(Point *ch,int len){ for(int i=0;i<len-2;i++) { double tmp = Cross(ch[i]-ch[i+2], ch[i+1]-ch[i+2]); if(tmp > eps) return; else if(tmp < -eps) { reverse(ch, ch+len); return; } }}//点p到直线ab的距离double DistanceToSegment(Point p, Point a, Point b){ if(a == b) return Length(p-a); Vector v1 = b-a, v2 = p-a, v3 = p-b; if(dcmp(Dot(v1, v2)) < 0) return Length(v2); else if(dcmp(Dot(v1, v3)) > 0) return Length(v3); else return fabs(Cross(v1, v2)) / Length(v1);}double dis_pair_seg(Point p1, Point p2, Point p3, Point p4){ return min(min(DistanceToSegment(p1, p3, p4), DistanceToSegment(p2, p3, p4)), min(DistanceToSegment(p3, p1, p2), DistanceToSegment(p4, p1, p2)));}double RC_Distance(Point *ch1, Point *ch2, int n, int m){ int q=0, p=0; REP(i, n) if(ch1[i].y-ch1[p].y < -eps) p=i; REP(i, m) if(ch2[i].y-ch2[q].y > eps) q=i; ch1[n]=ch1[0]; ch2[m]=ch2[0]; double tmp, ans=1e100; REP(i, n) { while((tmp = Cross(ch1[p+1]-ch1[p], ch2[q+1]-ch1[p]) - Cross(ch1[p+1]-ch1[p], ch2[q]- ch1[p])) > eps) q=(q+1)%m; if(tmp < -eps) ans = min(ans,DistanceToSegment(ch2[q],ch1[p],ch1[p+1])); else ans = min(ans,dis_pair_seg(ch1[p],ch1[p+1],ch2[q],ch2[q+1])); p=(p+1)%n; } return ans;}int n, m;Point ch1[10001], ch2[10001];int main(){ while(scanf("%d%d", &n, &m), n+m) { REP(i, n) scanf("%lf%lf", &ch1[i].x, &ch1[i].y); REP(i, m) scanf("%lf%lf", &ch2[i].x, &ch2[i].y); printf("%.5f\n", min(RC_Distance(ch1, ch2, n, m), RC_Distance(ch2, ch1, m, n))); } return 0;}