POJ3608(旋轉卡殼--求兩凸包的最近點對距離)

考慮如下的算法， 算法的輸入是兩個分別有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;
}