C++实现POJ 3608求两个凸包之间最短距离。

Question

C++实现POJ 3608求两个凸包之间最短距离。那代码应该是。

Answer 1

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1e4 + 10;
const double eps = 1e-8;
const double INF = 1e88;
struct node {
    double x,y;
}p[maxn],q[maxn];

node init;
int sgn (double x) {
    if (fabs (x) < eps) return 0;
    return x > 0 ? 1 : -1;
}
double cross (double x1,double y1,double x2,double y2) {
    return x1 * y2 - x2 * y1;
}

double muit (double x1,double y1,double x2,double y2) {
    return x1 * x2 + y1 * y2;
}

double dist (node a,node b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

bool cmp (const node a,const node b) {
    int sg = sgn (cross (a.x - init.x,a.y - init.y,b.x - init.x,b.y - init.y));
    if (sg == 0) return dist (a,init) < dist (b,init);
    return sg > 0;
}

double dist (node a,node b,node c) {
    if (dist (a,b) < eps) return dist (a,c);
    if (sgn(muit(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y)) < 0) return dist (a,c);
    if (sgn(muit(a.x - b.x, a.y - b.y, c.x - b.x, c.y - b.y) < 0)) return dist (b,c);
    return fabs (cross(c.x - a.x, c.y - a.y, b.x - a.x, b.y - a.y) / dist (a,b));
}

double ansdist (node a,node b,node c,node d) {
    return min (min (dist (a,b,c),dist (a,b,d)),min(dist (c,d,a),dist (c,d,b)));
}

void mysort (node a[],int n) {
    for (int i = 1;i <= n; ++ i) {
        if (a[i].y < a[1].y || (a[i].y == a[1].y && a[i].x < a[1].x)) {
            swap (a[1],a[i]);
        }
    }
    init = a[1];
//    printf ("%.3f  %.3f\n",init.x,init.y);
    sort (a + 1,a + 1 + n,cmp);
}
double rotating (node p[],node q[],int n,int m) {
    int miny = 1,maxy = 1;
    double mx = 0;
    p[n + 1] = p[1];
    q[m + 1] = q[1];
    for (int i = 1;i <= m; ++ i) {
        if (q[i].y > mx) {
            mx = q[i].y;
            maxy = i;
        }
    }
    double ans = dist (p[miny],q[maxy]);
    for (int i = 1;i <= n; ++ i) {
        while ((cross (q[maxy + 1].x - p[miny + 1].x,q[maxy + 1].y - p[miny + 1].y,p[miny].x - p[miny + 1].x,p[miny].y - p[miny + 1].y)-cross (q[maxy].x - p[miny + 1].x,q[maxy].y - p[miny + 1].y,p[miny].x - p[miny + 1].x,p[miny].y - p[miny + 1].y)) > eps) {
            maxy = maxy % m + 1;
        }
        ans = min (ans,ansdist (p[miny],p[miny + 1],q[maxy],q[maxy + 1]));
        miny = miny % n + 1;
    }
    return ans;
}

int main () {
    int n,m;
    while (scanf ("%d%d",&n,&m) && n) {
        for (int i = 1;i <= n; ++ i) {
            scanf ("%lf%lf",&p[i].x,&p[i].y);
        }
        for (int i = 1;i <= m; ++ i) {
            scanf ("%lf%lf",&q[i].x,&q[i].y);
        }
        mysort(p, n);
        mysort(q, m);
//        for (int i = 1;i <= m; ++ i) {
//            printf ("%.3f  %.3f\n",q[i].x,q[i].y);
//        }
        printf ("%.5f\n",min (rotating(p, q, n, m),rotating(q, p, m, n)));
    }
    return 0;
}