【問題描述】
最近對問題要求在包含有n個點的集合S中，找出距離最近的兩個點。設 p1(x1,y1)，p2(x2,y2)，……，pn(xn,yn)是平面的n個點。
嚴格地将，最近點對可能不止一對，此例輸出一對即可。
【基本算法思想】
暴力法：
在蠻力法實作最近點對問題中，将問題簡化：距離最近的點對可能多于一對，找出一對即可，另外隻考慮二維平面中的情況。此處考慮到
直接用公式計算其距離（歐幾裡得距離）：
算法分析與設計——最近點對問題 通過周遊所有點集，計算出每一個點對的距離，計算出最近的距離并輸出。避免同一對點計算兩次，隻考慮i<j的點對(pi,pj)。
其主要循環的步驟就是求出平方值，執行的次數為：
算法分析與設計——最近點對問題 分治法:
在利用分治法思想解決此問題時，首先考慮将最近對問題進行分治，設計其分治政策。将集合S分成兩個子集S1和S2，根據
平衡子問題原則，每個子集中的點數大緻都為n/2。這樣分治後，最近點對将會出現三種情況：在S1中，在S2中或者最近
點對分别在集合S1和S2中。利用遞歸分析法分别計算前兩種情況，第三種方法另外分析。求解出三類子情況後，
再合并三類情況，比較分析後輸出三者中最小的距離。
***複雜度分析***: 在分治算法中，當求解n個點的集合的最近點對時，對于上述三類情況中的前兩者可由遞歸算得，
而分析可得第三類情況的時間代價 ，合并後問題求解的總的時間按複雜度可由下列公式來：
算法分析與設計——最近點對問題 算法分析與設計——最近點對問題 【源代碼】
//最近點對問題，蠻力法實作(C++)
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<math.h>
#define MAX 99999
using namespace std;
double closestPoints(double x[],double y[],int n){
double x1,x2,y1,y2; //記錄下标
double dist,minDist=MAX;
for(int i=;i<n;i++)
for(int j=i+;j<n;j++){
dist=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]); //計算距離
if(dist<minDist){
minDist=dist;
x1=x[i];y1=y[i];
x2=x[j];y2=y[j];
}
}
cout<<"最近點對為：("<<x1<<","<<y1<<")-("<<x2<<","<<y2<<")"; //輸出坐标
return minDist;
}
int main(){
double x[],y[];
double minDist;
int n;
cout<<"輸入點的個數：\n";
cin>>n;
cout<<"輸入點集的坐标：\n";
for(int i=;i<n;i++)
cin>>x[i]>>y[i];
minDist=closestPoints(x,y,n);
cout<<"其距離為：\n"<<sqrt(minDist);
return ;
}
//分治法求解最近點對問題(C++)
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct point{ //點結構
double x,y;
};
double Distance(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b){ //按y升排序輔助函數
return a.y<b.y;
}
bool cmp2(point a,point b){ //按x升排序輔助函數
return a.x<b.x;
}
double closestPoint(point s[],int low,int high,point rec[]){
double d1,d2,d3,d;
int mid,i,j,index;
double x1,y1,x2,y2; //記錄點對的位置
point P[high-low+],temp1[],temp2[],temp3[]; //輔助空間
if(high-low==){ //兩個點的情況
rec[].x=s[low].x;rec[].y=s[low].y;
rec[].x=s[high].x;rec[].y=s[high].y;
return Distance(s[low],s[high]);
}
if(high-low==){ //三個點的情況
d1=Distance(s[low],s[low+]);
d2=Distance(s[low+],s[high]);
d3=Distance(s[low],s[high]);
if((d1<d2)&&(d1<d3)){
rec[].x=s[low].x;rec[].y=s[low].y;
rec[].x=s[low+].x;rec[].y=s[low+].y;
return d1;
}
else if(d2<d3){
rec[].x=s[low+].x;rec[].y=s[low+].y;
rec[].x=s[high].x;rec[].y=s[high].y;
return d2;
}
else {
rec[].x=s[low].x;rec[].y=s[low].y;
rec[].x=s[high].x;rec[].y=s[high].y;
return d3;
}
}
mid=(low+high)/; //其他情況遞歸
d1=closestPoint(s,low,mid,rec);
temp1[]=rec[];
temp1[]=rec[];
d2=closestPoint(s,mid+,high,rec);
temp2[]=rec[];
temp2[]=rec[];
if(d1<d2){
d=d1;
rec[]=temp1[];
rec[]=temp1[];
}
else {
d=d2;
rec[]=temp2[];
rec[]=temp2[];
}
index=;
for(i=mid;(i>=low)&&((s[mid].x-s[i].x)<d);i--) //點集合p1
P[index++]=s[i];
for(i=mid+;(i<=high)&&((s[i].x-s[mid].x)<d);i++) //點集合p2
P[index++]=s[i];
sort(P,P+index,cmp); //升序排列
for(i=;i<index;i++){
for(j=j+;j<index;i++){
if((P[j].y-P[i].y)>=d)
break;
else {
d3=Distance(P[i],P[j]);
if(d3<d){
rec[].x=P[i].x;rec[].y=P[i].y;
rec[].x=P[j].x;rec[].y=P[j].y;
d=d3;
}
}
}
}
return d;
}
int main(){
point p[]; //設定點的集合
int n;
double minDist;
cout<<"輸入點的個數：\n"; //輸入點的個數
cin>>n;
cout<<"輸入點集:（x,y）\n";
for(int i=;i<n;i++)
cin>>p[i].x>>p[i].y;
sort(p,p+n,cmp2); //對輸入的點先排序
point index[];
minDist=closestPoint(p,,n-,index);
cout<<"最小距離點對為：("<<index[].x<<","<<index[].y<<"),("<<index[].x<<","<<index[].y<<")\n";
cout<<"最小距離為：\n"<<minDist; //輸出點對的最小問題
return ;
}
