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;
}

补充：软件开发 , C++ ,

上一个：UVa 562: Dividing Coins
下一个：字符串消除