題目：Bridge Across Islands
?
分析：以下內(nèi)容來自：http://blog.csdn.net/acmaker/article/details/3178696
?
考慮如下的算法， 算法的輸入是兩個分別有m和n個順時針給定頂點(diǎn)的凸多邊形P和Q。
1.計算P上y坐標(biāo)值最小的頂點(diǎn)（稱為 yminP ）和Q上y坐標(biāo)值最大的頂點(diǎn)（稱為 ymaxQ）。
2.為多邊形在 yminP 和 ymaxQ 處構(gòu)造兩條切線 LP 和 LQ 使得他們對應(yīng)的多邊形位于他們的右側(cè)。
??此時 LP 和 LQ 擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個對踵點(diǎn)對。
3.計算距離(yminP,ymaxQ) 并且將其維護(hù)為當(dāng)前最小值。
4.順時針同時旋轉(zhuǎn)平行線直到其中一個與其所在的多邊形的邊重合。
5.如果只有一條線與邊重合， 那么只需要計算“頂點(diǎn)-邊”對踵點(diǎn)對和“頂點(diǎn)-頂點(diǎn)”對踵點(diǎn)對距離。 都將他們與當(dāng)前最小值
比較， 如果小于當(dāng)前最小值則進(jìn)行替換更新。如果兩條切線都與邊重合，那么情況就更加復(fù)雜了。如果邊“交疊”，也就是
可以構(gòu)造一條與兩條邊都相交的公垂線（但不是在頂點(diǎn)處相交）， 那么就計算“邊-邊”距離。 否則計算三個新的“頂點(diǎn)-頂
點(diǎn)”對踵點(diǎn)對距離。 所有的這些距離都與當(dāng)前最小值進(jìn)行比較， 若小于當(dāng)前最小值則更新替換。
6.重復(fù)執(zhí)行步驟4和步驟5， 直到新的點(diǎn)對為(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點(diǎn)到直線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));
}//求一條直線的兩端點(diǎn)到另外一條直線的距離，反過來一樣，共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;
}
?
超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生
總結(jié)
以上是生活随笔為你收集整理的POJ3608(旋转卡壳--求两凸包的最近点对距离)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
