【問題描述】

給定二維平面上n個點，找其中的一對點，使得在n個點組成的所有點對中，該點對間的距離最小。使用遞歸與分治策略求解二維平面上的最接近點對問題。假設所有點的集合為S，m為S中所有點的x坐標的中位數，垂直線x=m將集合S均勻分割為左右兩個子集合S1和S2。

[輸入]：

在屏幕上輸入點的個數，以及所有點的x和y坐標。

[輸出]：

第一次分割時，將所有點集合S分割為左右兩個子集合S1和S2，分別輸出左右子集合S1和S2，以及所有點集合S的最接近點對的距離以及最接近點對。

[樣例輸入]：

10

-15.4 -57.3

13.2 30.1

-87.5 93.2

47.6 -12.7

94.7 61.5

56.8 -57.1

27.8 43.5

-28.1 19.0

-96.2 47.5

55.5 -93.3

[樣例輸出]：

42.8

-28.1 19.0

13.2 30.1

36.2

55.5 -93.3

56.8 -57.1

19.8

13.2 30.1

27.8 43.5

[樣例說明]：

輸入：10個點，后續每行為每一點的x和y坐標。

輸出：左右子集合S1和S2，以及所有點集合S的最接近點對的距離以及最接近點對。例如，前面三行中，S1的最接近點對的距離為42.8，最接近點對的x和y坐標分別為(-28.1,19.0)和(13.2,30.1)。輸出最接近點對坐標時，先輸出的點的x坐標小于后輸出點的x坐標。中間三行和最后三行分別為子集合S2和集合S的最接近點對的距離以及最接近點對。

[問題分析]：

平面最近點對問題屬于遞歸與分治類問題，此問題可以從一維最近點對問題開始研究：

當我們處理一個一維最近點對問題時，通過遞歸與分治的思想，我們可以不斷對其進行二分，通過先對一維線上的點進行排序（此步驟是為了找中位數點的時候方便），然后找到這些點中的中位數mid，然后依此中位數為劃分標準，對所有的點集合進行二分，劃分為左集合和右集合，以此遞歸，在每層遞歸中，分別找到劃分的左右集合中的最近點對，并選出最近的那一點對，然后再檢查是否存在兩個點一個在左集合，一個在右集合而這兩點間的距離小于剛才找到的最近點對的距離（當然前人已經證明：如果最近點對出現在這種情況，在被劃分的左右集合中最多各有一個點）。

然后再將此情景推廣到二維平面點集合，劃分標準中位數mid則由點集合中每個點的x坐標來求，mid也可以被看作是一條垂直的線x=mid，將這個二維平面進行了劃分。接下來的步驟就跟一維最近點對問題的處理方法大致相同，不同的是，在出現最近點對的兩個點是一個位于左集合，一個位于右集合時，不再是在被劃分的左右集合中最多各有一個點，而是可能在左邊出現n/2個點，右邊最多出現6個點（這個結論前人也已經進行了證明）。

[算法步驟]：

1.將所有點按照x的進行排序

2.用x=mid將整個平面劃分為兩部分

3.求出x<=mid部分的最近點對距離d_left，求出x>mid部分的最近點對距離d_right，求出這兩者中最小的距離記為d

4.找出所有x坐標在(mid-d,mid+d)范圍中的點，放入res

5.對于(x,y),x∈(mid-d,mid)，如果點(x1,y1)中x1>mid且|y-y1|<d,那么記錄兩點間距離，如果小于d，那么更新d，否則檢查下一個點，以此類推，直至遍歷完res中所有的點。

[偽代碼]：

if(r-l==1) return dis(node[l],node[r])

if(r-l==2)?return min(dis(node[l],node[r]),min(dis(node[l],node[l+1]),dis(node[l+1],node[r])))

else

????????sort(node,node+n,by_X)

????????mid=(l+r)/2

????????d=min(closet(node,l,mid),closet(node,mid+1,r))

????????for i=l to r

????????????????if(fabs(node[i].x-node[mid].x)<d) res.push_back(node[i])

????????sort(res.begin(),res.end(),by_Y)

????????for i=0 to res.size

????????????????for j=i+1 to res.size

????????????????????????if(fabs(res[i].y-res[j].y)<d)

????????????????????????????????min_dis=dis(res[i],res[j])

????????????????????????????????if(min_dis<d) d=min_dis

[時間復雜度分析]：

T（n）=1 ??????????當k=2時

T（n）=2T(n/2)+n ??當k>2時

所以T（n）=O(nlog2n)

[代碼實現]：

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<bits/stdc++.h> using namespace std; typedef struct Point {double x,y; }Point;Point node[1000]; int n;double dis(Point a,Point b) {return sqrt(pow((a.x-b.x),2)+pow((a.y-b.y),2)); }bool by_X(Point a,Point b)//按x大小排序 {if(a.x==b.x) return a.y<b.y;else return a.x<b.x; }bool by_Y(Point a,Point b)//按y大小排序 {if(a.y==b.y) return a.x<b.x;else return a.y<b.y; }void swap(Point &a,Point &b) {Point c=a;a=b;b=c; } double closet(int l,int r,Point *best_node) {if(r-l==1)//兩個點的情況 {best_node[0]=node[l];best_node[1]=node[r]; return dis(node[l],node[r]);}else if(r-l==2)//三個點的情況 {double dis1=dis(node[l],node[l+1]);double dis2=dis(node[l+1],node[r]);double dis3=dis(node[l],node[r]);if(dis1<dis2&&dis1<dis3){best_node[0]=node[l];best_node[1]=node[l+1];return dis1;}if(dis2<dis1&&dis2<dis3){best_node[0]=node[l+1];best_node[1]=node[r];return dis2;}if(dis3<dis2&&dis3<dis1){best_node[0]=node[l];best_node[1]=node[r];return dis3;}}else//大于三個點的情況 { int mid=(l+r)/2;Point temp1[2],temp2[2];double d_left=closet(l,mid,best_node);temp1[0]=best_node[0];temp1[1]=best_node[1];if(mid==(0+n-1)/2) //為了保證是在最外一層遞歸（即第一次分割的時候）的時候再輸出 {printf("%.1lf\n",d_left);if(temp1[0].x>temp1[1].x) swap(temp1[0],temp1[1]);printf("%.1lf %.1lf\n",temp1[0].x,temp1[0].y);printf("%.1lf %.1lf\n",temp1[1].x,temp1[1].y);} double d_right=closet(mid+1,r,best_node);temp2[0]=best_node[0];temp2[1]=best_node[1];if(mid==(0+n-1)/2) {printf("%.1lf\n",d_right);if(temp2[0].x>temp2[1].x) swap(temp2[0],temp2[1]);printf("%.1lf %.1lf\n",temp2[0].x,temp2[0].y);printf("%.1lf %.1lf\n",temp2[1].x,temp2[1].y);}double d;if(d_left<=d_right){d=d_left;best_node[0]=temp1[0];best_node[1]=temp1[1];}if(d_left>d_right){d=d_right;best_node[0]=temp2[0];best_node[1]=temp2[1];} vector<Point> res;for(int i=l;i<=r;i++)//將距離mid距離小于d的點放入res {if(fabs(node[i].x-node[mid].x)<d){res.push_back(node[i]);}}sort(res.begin(),res.end(),by_Y);//將res中的點按照y的大小進行排序，便于后面的篩選 for(int i=0;i<res.size();i++)//通過i，j遍歷res中所有的點對，從而找到距離最近的點對 {for(int j=i+1;j<res.size();j++){if(fabs(res[i].y-res[j].y)>d) break;double min_dis=dis(res[i],res[j]);if(min_dis<d){d=min_dis;best_node[0]=res[i];best_node[1]=res[j];}}} return d; }} int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;double d;for(int i=0;i<n;i++){cin>>node[i].x;cin>>node[i].y;} Point best_node[2];//記錄最近點對 sort(node,node+n,by_X);d=closet(0,n-1,best_node); printf("%.1lf\n",d);if(best_node[0].x>best_node[1].x) swap(best_node[0],best_node[1]);printf("%.1lf %.1lf\n",best_node[0].x,best_node[0].y);printf("%.1lf %.1lf",best_node[1].x,best_node[1].y);}

總結

以上是生活随笔為你收集整理的【算法分析与设计】平面最近点对（含最近距离、最近点对、第一次分割点集合的输出）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。