POJ 3608 旋转卡壳

思路：

旋转卡壳应用

注意点&边  边&边  点&点 三种情况

//By SiriusRen

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

const double eps=1e-;

const int N=;

typedef double db;

int n,m;

struct P{db x,y;P(){}P(db X,db Y){x=X,y=Y;}}p1[N],p2[N];

P operator-(P a,P b){return P(a.x-b.x,a.y-b.y);}

db operator*(P a,P b){return a.x*b.y-a.y*b.x;}

db operator^(P a,P b){return a.x*b.x+a.y*b.y;}

db dis(P c){return sqrt(c.x*c.x+c.y*c.y);}

db dotc(P a,P b,P c){return (b-a)^(c-a);}

db difc(P a,P b,P c){return (b-a)*(c-a);}

db p2seg(P a,P b,P c){

    if(dotc(a,b,c)<-eps)return dis(a-c);

    if(dotc(b,a,c)<-eps)return dis(b-c);

    return abs(difc(a,b,c)/dis(a-b));

}

db seg2seg(P a,P b,P c,P d){

    return min(min(p2seg(a,b,c),p2seg(a,b,d)),min(p2seg(c,d,a),p2seg(c,d,b)));

}

double solve(P p[],P q[],int np,int nq){

    int sp=,sq=;

    for(int i=;i<=np;i++)if(p[i].y<p[sp].y)sp=i;

    for(int i=;i<=nq;i++)if(q[i].y>q[sq].y)sq=i;

    p[np+]=p[],q[nq+]=q[];

    double tmp,ans=1e9;

    for(int i=;i<=np;i++){

        while(tmp=(difc(p[sp+],q[sq+],p[sp])-difc(p[sp+],q[sq],p[sp]))>eps)sq=sq%nq+;

        if(tmp<-eps)ans=min(ans,p2seg(p[sp],p[sp+],q[sq]));

        else ans=min(ans,seg2seg(p[sp],p[sp+],q[sq],q[sq+]));

        sp=sp%np+;

    }return ans;

}

int main(){

    while(scanf("%d%d",&n,&m)&&(n||m)){

        for(int i=;i<=n;i++)scanf("%lf%lf",&p1[i].x,&p1[i].y);

        for(int i=;i<=m;i++)scanf("%lf%lf",&p2[i].x,&p2[i].y);

        printf("%lf\n",min(solve(p1,p2,n,m),solve(p2,p1,m,n)));

    }

}