最遠(yuǎn)點(diǎn)對(duì)問(wèn)題
類似于“最近點(diǎn)對(duì)問(wèn)題”，這個(gè)問(wèn)題也可以用枚舉的方法求解，時(shí)間復(fù)雜度O(n^2)。假設(shè)平面上有n個(gè)點(diǎn)，那么這一對(duì)最遠(yuǎn)點(diǎn)必然存在于這n個(gè)點(diǎn)所構(gòu)成的一
個(gè)凸包上，為了降低時(shí)間復(fù)雜度，可以先將這n個(gè)點(diǎn)按極角排序，然后利用Graham_scan法求出這個(gè)凸包，再枚舉凸包上的所有頂點(diǎn)(也可以用旋轉(zhuǎn)卡
殼)求出這個(gè)最遠(yuǎn)距離，時(shí)間復(fù)雜度O(nlogn)。再最壞的情況下，如果這n個(gè)點(diǎn)本身就構(gòu)成了一個(gè)凸包，時(shí)間復(fù)雜度為O(n^2)。該算法的平均復(fù)雜度
為O(nlogn)。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
const int MAXN = 100001;
const double eps = 1e-6;
struct point{
double x,y;
}p[MAXN],h[MAXN];
inline double distance(const point &p1,const point &p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
inline double multiply(const point &sp,const point &ep,const point &op){
return ((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y));
}
int cmp(const void *a,const void *b){
point *p1 = (point *)a;
point *p2 = (point *)b;
double t = (p1->y-p[0].y)*(p2->x-p[0].x)-(p2->y-p[0].y)*(p1->x-p[0].x);
if(t>eps) return 1;
else if(fabs(t)<=eps) return 0;
else return -1;
}
void anglesort(point p[],int n){
int i,k=0;
point temp;
for(i=1;i<n;i++)
if(p[i].x<p[k].x || (p[i].x==p[k].x) && (p[i].y<p[k].y))
k=i;
temp=p[0],p[0]=p[k],p[k]=temp;
qsort(p+1,n-1,sizeof(point),cmp);
}
void Graham_scan(point p[],point ch[],int n,int &len){
int i,top=2;
anglesort(p,n);
if(n<3){
for(i=0,len=n;i<n;i++) ch[i]=p[i];
return;
}
ch[0]=p[0],ch[1]=p[1],ch[2]=p[2];
for(i=3;i<n;i++){
while(multiply(p[i],ch[top],ch[top-1])>=0) top--;
ch[++top]=p[i];
}
len=top+1;
}
int main(){
int i,j,n,len;
double d,ans;
while(scanf("%d",&n),n){
for(i=0;i<n;i++) scanf("%lf %lf",&p[i].x,&p[i].y);
Graham_scan(p,h,n,len);
for(ans=i=0;i<len;i++)
for(j=i+1;j<len;j++){
d=distance(h[i],h[j]);
if(d>ans) ans=d;
}
printf("%.2lf\n",ans);
}
return 0;
}
接下來(lái)所謂旋轉(zhuǎn)卡殼法（類似求數(shù)組中最長(zhǎng)子段的和）：
int main(){
while(~scanf("%d", &n)) {
for(int i = 0; i < n; i ++)
p[i].read();
int top = 0;
tubao(p, id, n, top);
int area, area2, i, j, k, t, maxx = 0;
for(i = 0, k = 2; i < top; i ++){
j = (i + 1) % top;
t = (k + 1) % top;
area = fabs(xmul(p[id[i]], p[id[k]], p[id[j]]));
area2 = fabs(xmul(p[id[i]], p[id[t]], p[id[j]]));
while(area < area2){
area = area2;
k = (k + 1) % top;
t = (k + 1) % top;
area2 = fabs(xmul(p[id[i]], p[id[t]], p[id[j]]));
maxx = max(maxx, max( dist(p[id[i]], p[id[k]]), dist(p[id[i]], p[id[t]]) ));
}
}
if(maxx != 0)
printf("%lf\n", maxx);
else
printf("%lf\n", dist(p[id[0]], p[id[top-1]]));
}
}