?????http://acm.hdu.edu.cn/showproblem.php?pid=1007

???????? 先說下題意，很簡單，給n個點的坐標，求距離最近的一對點之間距離的一半。第一行是一個數n表示有n個點，接下來n行是n個點的x坐標和y坐標，實數。
????? 這個題目其實就是求最近點對的距離。《算法導論》上有詳細講解，王曉東的書上也有代碼。主要思想就是分治。先把n個點按x坐標排序，然后求左邊n/2個和右邊n/2個的最近距離，最后合并。合并要重點說一下，比較麻煩。
????? 首先，假設點是n個，編號為1到n。我們要分治求，則找一個中間的編號mid，先求出1到mid點的最近距離設為d1，還有mid+1到n的最近距離設為d2。這里的點需要按x坐標的順序排好，并且假設這些點中，沒有2點在同一個位置。（若有，則直接最小距離為0了）。
????? 然后，令d為d1, d2中較小的那個點。如果說最近點對中的兩點都在1-mid集合中，或者mid+1到n集合中，則d就是最小距離了。但是還有可能的是最近點對中的兩點分屬這兩個集合，所以我們必須先檢測一下這種情況是否會存在，若存在，則把這個最近點對的距離記錄下來，去更新d。這樣我們就可以得道最小的距離d了。
????? 關鍵是要去檢測最近點對，理論上每個點都要和對面集合的點匹配一次，那效率還是不能滿足我們的要求。所以這里要優化。怎么優化呢？考慮一下，假如以我們所選的分割點mid為界，如果某一點的橫坐標到點mid的橫坐標的絕對值超過d1并且超過d2，那么這個點到mid點的距離必然超過d1和d2中的小者，所以這個點到對方集合的任意點的距離必然不是所有點中最小的。
????? 所以我們先把在mid為界左右一個范圍內的點全部篩選出來，放到一個集合里。篩選好以后，當然可以把這些點兩兩求距離去更新d了，不過這樣還是很慢，萬一滿足條件的點很多呢。這里還得繼續優化。首先把這些點按y坐標排序。假設排序好以后有cnt個點，編號為0到cnt-1。那么我們用0號去和1到cnt-1號的點求一下距離，然后1號和2到cnt-1號的點求一下距離。。。如果某兩個點y軸距離已經超過了d，這次循環就可以直接break了，開始從下一個點查找了。

// 分治算法求最近點對 #include<iostream> #include<algorithm> #include<cmath> using namespace std;struct point {double x , y; }p[100005];int a[100005]; //保存篩選的坐標點的索引int cmpx(const point &a , const point &b) {return a.x < b.x; } int cmpy(int &a , int &b) //這里用的是下標索引 {return p[a].y < p[b].y; } inline double dis(point &a , point &b) {return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } inline double min(double a , double b) {return a < b ? a : b; } double closest(int low , int high) {if(low + 1 == high)return dis(p[low] , p[high]);if(low + 2 == high)return min(dis(p[low] , p[high]) , min( dis(p[low] , p[low+1]) , dis(p[low+1] , p[high]) ));int mid = (low + high)>>1;double ans = min( closest(low , mid) , closest(mid + 1 , high) ); //分治法進行遞歸求解int i , j , cnt = 0;for(i = low ; i <= high ; ++i) //把x坐標在p[mid].x-ans~p[mid].x+ans范圍內的點取出來 {if(p[i].x >= p[mid].x - ans && p[i].x <= p[mid].x + ans)a[cnt++] = i; //保存的是下標索引}sort(a , a + cnt , cmpy); //按y坐標進行升序排序 for(i = 0 ; i < cnt ; ++i){for(j = i+1 ; j < cnt ; ++j){if(p[a[j]].y - p[a[i]].y >= ans) //注意下標索引break;ans = min(ans , dis(p[a[i]] , p[a[j]]));}}return ans; } int main(void) {int i,n;while(scanf("%d",&n) != EOF){if(!n)break;for(i = 0 ; i < n ; ++i)scanf("%lf %lf",&p[i].x,&p[i].y);sort(p , p + n , cmpx);printf("%.2lf\n",closest(0 , n - 1)/2); }return 0; }

按照y值進行升序排列后，還可以進一步進行優化的，就是每次選取7個點就OK了，具體原因編程之美上面有介紹的。

for(i = 0 ; i < cnt ; ++i){int k = (i+7) > cnt ? cnt :(i+7); //只要選取出7個點(證明過程沒看懂) for(j = i+1 ; j < k ; ++j){if(p[a[j]].y - p[a[i]].y >= ans) //注意下標索引break;ans = min(ans , dis(p[a[i]] , p[a[j]]));}}

總結

以上是生活随笔為你收集整理的分治算法求最近点对的全部內容，希望文章能夠幫你解決所遇到的問題。

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