POJ 3608 Bridge Across Islands(旋转卡壳)

转载:http://www.hankcs.com/program/algorithm/poj-3608-bridge-across-islands.html
跨岛大桥：在两个凸包小岛之间造桥，求最小距离？
  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 #include <cmath>
  5 using namespace std;
  6  
  7 #define MAX_N 10000 + 16
  8 #define INF 0x3F3F3F3F
  9 #define EPS 1E-10
 10  
 11 struct Point
 12 {
 13     double x, y;
 14     Point() {}
 15     Point(double x, double y) : x(x), y(y) {}
 16     Point operator + (const Point& p){ return Point(x + p.x, y + p.y); }
 17     Point operator - (const Point& p){ return Point(x - p.x, y - p.y); }
 18     Point operator * (const double& d){ return Point(x * d, y * d); }
 19     bool operator < (const Point& a) const
 20     {
 21         if (x != a.x) return x < a.x;
 22         else return y < a.y;
 23     }
 24     double dot(const Point& p) { return x * p.x + y * p.y; }
 25     double det(const Point& p) { return x * p.y - y * p.x; }
 26 };
 27  
 28 Point P[MAX_N], Q[MAX_N];
 29  
 30 // 向量AB 与 AC 的叉积 如果叉积大于0，那么C在向量AB的逆时针方向，叉积小于0则在AB的顺时针方向。如果叉积等于0，则ABC共线。
 31 inline double cross(Point A, Point B, Point C)
 32 {
 33     return (B - A).det(C - A);
 34 }
 35  
 36 // 向量AB 与 AC 的点积 如果点积的结果为0，那么这两个向量互相垂直
 37 inline double multi(Point A, Point B, Point C)
 38 {
 39     return (B - A).dot(C - A);
 40 }
 41  
 42 // 两点距离
 43 inline double dist(Point A, Point B)
 44 {
 45     return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
 46 }
 47  
 48 // 逆时针排序
 49 inline void anticlockwise_sort(Point* p, int N)
 50 {
 51     for (int i = 0; i < N - 2; ++i)
 52     {
 53         double tmp = cross(p[i], p[i + 1], p[i + 2]);
 54         if (tmp > EPS) return;
 55         else if (tmp < -EPS)
 56         {
 57             reverse(p, p + N);
 58             return;
 59         }
 60     }
 61 }
 62  
 63 //计算C点到线段AB的最短距离
 64 inline double point_to_line(Point A, Point B, Point C)
 65 {
 66     if (dist(A, B) < EPS) return dist(B, C);
 67     if (multi(A, B, C) < -EPS) return dist(A, C);
 68     if (multi(B, A, C) < -EPS) return dist(B, C);
 69     return fabs(cross(A, B, C) / dist(A, B));
 70 }
 71  
 72 //求一条线段的两端点到另外一条线段的距离，反过来一样，共4种情况
 73 inline double line_to_line(Point A, Point B, Point C, Point D)
 74 {
 75     return min(min(point_to_line(A, B, C), point_to_line(A, B, D)), min(point_to_line(C, D, A), point_to_line(C, D, B)));
 76 }
 77  
 78 double solve(Point* P, Point* Q, int n, int m)
 79 {
 80     int yminP = 0, ymaxQ = 0;
 81     for (int i = 0; i < n; ++i) if (P[i].y < P[yminP].y) yminP = i;    // P上y坐标最小的顶点
 82     for (int i = 0; i < m; ++i) if (Q[i].y > Q[ymaxQ].y) ymaxQ = i; // Q上y坐标最大的顶点
 83     P[n] = P[0];    // 为了方便，避免求余
 84     Q[m] = Q[0];
 85     double arg, ans = INF;
 86     for (int i = 0; i < n; ++i)
 87     {
 88         while (arg = cross(P[yminP + 1], Q[ymaxQ + 1], P[yminP]) - cross(P[yminP + 1], Q[ymaxQ], P[yminP]) > EPS) ymaxQ = (ymaxQ + 1) % m;
 89         ans = min(ans, line_to_line(P[yminP], P[yminP + 1], Q[ymaxQ], Q[ymaxQ + 1]));
 90         yminP = (yminP + 1) % n;
 91     }
 92     return ans;
 93 }
 94  
 95  
 96 ///////////////////////////SubMain//////////////////////////////////
 97 int main(int argc, char *argv[])
 98 {
 99 #ifndef ONLINE_JUDGE
100     freopen("in.txt", "r", stdin);
101     freopen("out.txt", "w", stdout);
102 #endif
103     int N, M;
104     while (~scanf("%d%d", &N, &M) && N + M)
105     {
106         for (int i = 0; i < N; ++i)
107         {
108             scanf("%lf%lf", &P[i].x, &P[i].y);
109         }
110         for (int i = 0; i < M; ++i)
111         {
112             scanf("%lf%lf", &Q[i].x, &Q[i].y);
113         }
114         anticlockwise_sort(P, N);
115         anticlockwise_sort(Q, M);
116         printf("%.5lf
", solve(P, Q, N, M));
117     }
118 #ifndef ONLINE_JUDGE
119     fclose(stdin);
120     fclose(stdout);
121     system("out.txt");
122 #endif
123     return 0;
124 }