POJ 3608 Bridge Across Islands （旋转卡壳）

【题目大意】

　　求出两个凸包之间的最短距离

【题解】

　　我们先找到一个凸包的上顶点和一个凸包的下定点，以这两个点为起点向下一个点画线，
　　做旋转卡壳，答案一定包含在这个过程中

【代码】

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

using namespace std;

double EPS=1e-10;

const double INF=0x3F3F3F3F;

const double PI=acos(-1.0);

double add(double a,double b){

    if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;

    return a+b;

}

struct P{

    double x,y;

    P(){}

    P(double x,double y):x(x),y(y){}

    P operator + (P p){return P(add(x,p.x),add(y,p.y));}

    P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}

    P operator * (double d){return P(x*d,y*d);}

    double dot(P p){return add(x*p.x,y*p.y);} //点积

    double det(P p){return add(x*p.y,-y*p.x);}  //叉积

};

bool cmp_y(const P& p,const P& q){

    if(p.y!=q.y)return p.y<q.y;

    return p.x<q.x;

}

double dist(P p,P q){return sqrt((p-q).dot(p-q));}

double cross(P a, P b,P c){return(b-a).det(c-a);}

double multi(P a,P b,P c){return(b-a).dot(c-a);}

// 点到线段距离

double point_to_line(P a,P b,P c){

    if(dist(a,b)<EPS)return dist(b,c);

    if(multi(a,b,c)<-EPS)return dist(a,c);

    if(multi(b,a,c)<-EPS)return dist(b,c);

    return fabs(cross(a,b,c)/dist(a,b));

}

// 线段到线段距离

double line_to_line(P A,P B,P C,P D){

    double a=point_to_line(A,B,C);

    double b=point_to_line(A,B,D);

    double c=point_to_line(C,D,A);

    double d=point_to_line(C,D,B);

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

}

void anticlockwise_sort(P* p,int N){

    for(int i=0;i<N-2;i++){

        double tmp=cross(p[i],p[i+1],p[i+2]);

        if(tmp>EPS)return;

        else if(tmp<-EPS){

            reverse(p,p+N);

            return;

        }

    }

}

const int MAX_N=10000;

int n,m;

P ps[MAX_N],qs[MAX_N];

void solve(){

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

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

    anticlockwise_sort(ps,n);

		anticlockwise_sort(qs,m);

		int i=0,j=0;

		for(int k=0;k<n;k++)if(!cmp_y(ps[i],ps[k]))i=k;

    for(int k=0;k<n;k++)if(cmp_y(qs[j],qs[k]))j=k;

    double res=INF;

    ps[n]=ps[0]; qs[m]=qs[0];

    for(int k=0;k<n;k++){

    	while(cross(ps[i+1],qs[j+1],ps[i])-cross(ps[i+1],qs[j],ps[i])>EPS)j=(j+1)%m;

        res=min(res,line_to_line(ps[i],ps[i+1],qs[j],qs[j+1]));

        i=(i+1)%n;

    }printf("%.5lf\n",res);

}

int main(){

    while(~scanf("%d%d",&n,&m)&&n+m)solve();

    return 0;

}

秒客网

POJ 3608 Bridge Across Islands （旋转卡壳）

相关文章