插眼大佬博客：最近點對算法模板 - WThhhhh20 - 博客園

用法：將N個點讀入后用cmpx函數排序，然后直接調用findMin函數即可，參數為(0,n-1)，時間復雜度為nlogn

代碼：

const int N=1e5+100;//點的數量struct Point {double x,y; }point[N];int y_sort[N];int cmpx(Point a,Point b)//按照x對這些點從小到大排序 {return a.x<b.x; }int cmpy(int a,int b)//對最近點算法中的y_sort數組排序 {return point[a].y<point[b].y; }double dis(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } /*最近點對算法,在point[first]--point[last]個點中尋找一個最短距離使用該算法前先對這些點排序sort(point,point+n,cmpx); */ double findMin(int first, int last) {if((last-first)==1)return dis(point[first],point[last]);else if(last-first==2){double d1 = dis(point[first],point[first+1]);double d2 = dis(point[first],point[first+2]);double d3 = dis(point[first+1],point[first+2]);return min(min(d1,d2),d3);}//二分int mid = (first+last)/2;double min_dist = min(findMin(first,mid),findMin(mid+1,last));if(min_dist==0)return 0;int y_end = 0;for(int i=mid;point[mid].x-point[i].x<min_dist&&i>=first;i--)y_sort[y_end++]=i;for(int i=mid+1;point[i].x-point[mid+1].x<min_dist&&i<=last;i++)y_sort[y_end++]=i;sort(y_sort,y_sort+y_end,cmpy);for(int i=0;i<y_end;i++)for(int j=i+1;j<y_end&&(point[y_sort[j]].y-point[y_sort[i]].y)<min_dist;j++)min_dist=min(min_dist,dis(point[y_sort[i]],point[y_sort[j]]));return min_dist; }

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的(转)二维平面坐标系-最近点对模板的全部內容，希望文章能夠幫你解決所遇到的問題。

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