POJ3608(旋转卡壳--求两凸包的最近点对距离)

曾经终败给现在 2021-12-14 00:33 351阅读 0赞

[**题目：Bridge Across Islands**][Bridge Across Islands]

**分析：以下内容来自：**[**http://blog.csdn.net/acmaker/article/details/3178696**][http_blog.csdn.net_acmaker_article_details_3178696]

**考虑如下的算法， 算法的输入是两个分别有m和n个顺时针给定顶点的凸多边形P和Q。**

**1.计算P上y坐标值最小的顶点（称为 yminP ）和Q上y坐标值最大的顶点（称为 ymaxQ）。**

**2.为多边形在 yminP 和 ymaxQ 处构造两条切线 LP 和 LQ 使得他们对应的多边形位于他们的右侧。**

**此时 LP 和 LQ 拥有不同的方向， 并且 yminP 和 ymaxQ 成为了多边形间的一个对踵点对。**

**3.计算距离(yminP,ymaxQ) 并且将其维护为当前最小值。**

**4.顺时针同时旋转平行线直到其中一个与其所在的多边形的边重合。**

**5.如果只有一条线与边重合， 那么只需要计算“顶点-边”对踵点对和“顶点-顶点”对踵点对距离。 都将他们与当前最小值**

**比较， 如果小于当前最小值则进行替换更新。如果两条切线都与边重合，那么情况就更加复杂了。如果边“交叠”，也就是**

**可以构造一条与两条边都相交的公垂线（但不是在顶点处相交）， 那么就计算“边-边”距离。 否则计算三个新的“顶点-顶**

**点”对踵点对距离。 所有的这些距离都与当前最小值进行比较， 若小于当前最小值则更新替换。**

**6.重复执行步骤4和步骤5， 直到新的点对为(yminP,ymaxQ)。**

**7.输出最小距离。**

#include <iostream>
    #include <string.h>
    #include <algorithm>
    #include <stdio.h>
    #include <math.h>
    
    using namespace std;
    
    const int N=50000;
    const double eps=1e-9;
    const double INF=1e99;
    
    struct Point
    {
        double x,y;
    };
    
    Point P[N],Q[N];
    
    double cross(Point A,Point B,Point C)
    {
        return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
    }
    
    double dist(Point A,Point B)
    {
        return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
    }
    
    double multi(Point A,Point B,Point C)
    {
        return (B.x-A.x)*(C.x-A.x)+(B.y-A.y)*(C.y-A.y);
    }
    
    //顺时针排序
    void anticlockwise(Point 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;
            }
        }
    }
    
    //计算C点到直线AB的最短距离
    double Getdist(Point A,Point B,Point 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));
    }
    
    //求一条直线的两端点到另外一条直线的距离，反过来一样，共4种情况
    double MinDist(Point A,Point B,Point C,Point D)
    {
        return min(min(Getdist(A,B,C),Getdist(A,B,D)),min(Getdist(C,D,A),Getdist(C,D,B)));
    }
    
    double Solve(Point P[],Point Q[],int n,int m)
    {
        int yminP=0,ymaxQ=0;
        for(int i=0;i<n;i++)
           if(P[i].y<P[yminP].y)
              yminP=i;
        for(int i=0;i<m;i++)
           if(Q[i].y>Q[ymaxQ].y)
              ymaxQ=i;
        P[n]=P[0];
        Q[m]=Q[0];
        double tmp,ans=INF;
        for(int i=0;i<n;i++)
        {
            while(tmp=cross(P[yminP+1],Q[ymaxQ+1],P[yminP])-cross(P[yminP+1],Q[ymaxQ],P[yminP])>eps)
                ymaxQ=(ymaxQ+1)%m;
            if(tmp<-eps) ans=min(ans,Getdist(P[yminP],P[yminP+1],Q[ymaxQ]));
            else         ans=min(ans,MinDist(P[yminP],P[yminP+1],Q[ymaxQ],Q[ymaxQ+1]));
            yminP=(yminP+1)%n;
        }
        return ans;
    }
    
    int main()
    {
        int n,m;
        while(cin>>n>>m)
        {
            if(n==0&&m==0) break;
            for(int i=0;i<n;i++)
               cin>>P[i].x>>P[i].y;
            for(int i=0;i<m;i++)
               cin>>Q[i].x>>Q[i].y;
            anticlockwise(P,n);
            anticlockwise(Q,m);
            printf("%.5lf\n",min(Solve(P,Q,n,m),Solve(Q,P,m,n)));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/james1207/p/3265456.html

[Bridge Across Islands]: http://poj.org/problem?id=3608
[http_blog.csdn.net_acmaker_article_details_3178696]: http://blog.csdn.net/acmaker/article/details/3178696