支持本站請點閱廣告,感恩:)

給定一些二維平面上的點座標,求出「距離最近的兩點」的距離為多少。

( Given a set of points in a two dimensional space, you will have to find the distance between the closest two points.)

Input

輸入包含好幾組測試資料,每組的第1列有一個整數N(0 <= N <=10000),代表此組測試資料共有幾個點。接下來的N列每列有2個數,分別代表代表某一個點的x和y座標。N=0時代表輸入結束。座標的值均小於40000並且不會是負的數。

(The input file contains several sets of input. Each set of input starts with an integer N(0 ≤ N ≤ 10000), which denotes the number of points in this set. The next N line contains the coordinates of N twodimensional points. The first of the two numbers denotes the X-coordinate and the latter denotes the Y -coordinate. The input is terminated by a set whose N = 0. This set should not be processed. The value of the coordinates will be less than 40000 and non-negative.)

Output

對於每組測試資料,請輸出2點間最小的距離(輸出到小數點後4位)。如果任2點間的距離都不小於10000,請輸出 INFINITY 

(For each set of input produce a single line of output containing a floating point number (with four digits after the decimal point) which denotes the distance between the closest two points. If there is no such two points in the input whose distance is less than 10000, print the line ‘INFINITY’. Sample Input)

Sample input

3
0 0
10000 10000
20000 20000
5
0 2
6 67
43 71
39 107
189 140
0

Sample Output

INFINITY
36.2215

Closest Pair

Closest Pair

一群點當中,距離最近的兩個點叫作「最近點對」。

演算法( Enumeration )

窮舉法的時間複雜度是 O(N^2) ,可以找出所有的最近點對。

 
  1. struct Point {double xy;} p[10];
  2.  
  3. double closest_pair()
  4. {
  5.     double d = 1e9// 最近點對的距離
  6.     Segment cp[10]; // 最近點對
  7.     int n = 0;      // 最近點對的數目
  8.  
  9.     for (int i=0i<N; ++i)         // 窮舉a點
  10.         for (int j=i+1j<N; ++j)   // 窮舉b點
  11.         {
  12.             double dij = distance(p[i], p[j]);
  13.             if (dij < d)
  14.             {
  15.                 d = dij;
  16.                 n = 0;
  17.                 cp[n++] = Segment(ij);
  18.             }
  19.             else (dij == d)
  20.                 cp[n++] = Segment(ij);
  21.         }
  22.  
  23.     return d;
  24. }

實作時,減少 sqrt 函式的呼叫次數,盡量紀錄距離的平方,可以減少計算時間。

演算法( Sweep Line )

預先按照水平座標排序,再以水平距離裁減搜尋範圍。

一、先排序所有點,以X座標為主,Y座標無所謂。
二、從左往右掃,依序窮舉各點作為左端點。
 甲、從左端點開始往右掃,依序窮舉各點作為右端點。
 乙、若左右兩點距離差太遠、超過目前發現的最近點對距離,
   就可以停止窮舉右端點。

也可以先窮舉右端點、再窮舉左端點。下個段落會用到。

最差情況是所有點都在同一條垂直線上,將會窮舉到所有點對,完全無法裁減搜尋範圍。儘管時間複雜度仍是 O(N^2) ,但是實際效率極佳。

 
  1. struct Point {double xy;} p[10];
  2. bool cmp(const Pointiconst Pointj) {return i.x < j.x;}
  3.  
  4. double closest_pair()
  5. {
  6.     sort(pp+10cmp); // 依X座標排序
  7.  
  8.     double d = 1e9;     // 最近點對的距離
  9.     Segment cp[10];     // 最近點對
  10.     int n = 0;          // 最近點對的數目
  11.  
  12.     for (int i=0i<N; ++i)
  13.         for (int j=i+1j<N; ++j)
  14.         {
  15.             if (p[i].x + d < p[j].xbreak;
  16.             double dij = distance(p[i], p[j]);
  17.             if (dij < d)
  18.             {
  19.                 d = dij;
  20.                 n = 0;
  21.                 cp[n++] = Segment(ij);
  22.             }
  23.             else (dij == d)
  24.                 cp[n++] = Segment(ij);
  25.         }
  26.  
  27.     return d;
  28. }

實作時,避免直接排序原資料,複製一份指標或索引值來排序,可以減少計算時間。

UVa 10245 10750 11378 ICPC 6666

演算法( Sweep Line )

要避免最差情況,有個想法是:再將所有點依照垂直方向排序。如此一來,時間複雜度得降低為 O(NlogN) 。

一、位於右端點左方、距離 d 以下的點,才有可能形成最近點對。也就是以右端點為圓心、左半圓涵蓋的點(包含邊界)。照理來說,我們只需要檢查半圓範圍裡面的點。

運用左掃描線作為輔助,跟隨右掃描線亦步亦趨,我們得以輕易的過濾出水平距離 d 以下的點,但是無法進一步過濾出半徑距離 d 以下的點。

折衷的方式是依照 Y 座標排序水平距離 d 以下的點,然後運用二分搜尋法找到右端點,然後找到 Y 座標比右端點稍大、稍小的點──這些點很可能就在半圓之內。

二、右端點左方的點,兩兩之間的距離,至少是 d 。

點與點之間無法太過密集擁擠,能夠組成最近點對的左端點並不多。其實只需檢查右端點的前兩點、後兩點,作為左端點,就能囊括所有最近點對!

最極端的情況,是以右端點為中心、左半正方形涵蓋的點(包含邊界)。

由於右掃描線不斷往右移動,水平距離 d 以下的點必須不斷重新排序,很花時間。運用 Binary Tree 資料結構,即可隨時保持排序,節省時間。

一、預先排序所有點,X座標為主,Y座標為輔。
二、建立一棵平衡二元樹(AVL Tree),
  儲存右端點的左方、水平距離小於等於d的點。
  二元樹排序以Y座標為主,X座標為輔。一開始是空的。
  d是當下的最近點對距離。一開始是無限大。
三、右掃描線依序窮舉各點作為右端點。
 甲、二元樹刪除與右端點水平距離大於d的點們。
   (左掃描線視情況往右移動。)
 乙、二元樹加入右端點。
 丙、二元樹尋找右端點的前兩點與後兩點,嘗試更新最近點對。

掃描線輔以資料結構,是計算幾何的經典手法,請讀者牢記在心。

時間複雜度。排序 O(NlogN) 。掃描線 O(N) 。二元樹總共刪除 N 個點、加入 N 個點、尋找 5N 個點, O(NlogN) 。

【待補程式碼】

演算法( Divide and Conquer )

時間複雜度是 O(N * (logN)^2) ,可以找出所有的最近點對。原理是把平面切割成左右兩側,答案分為「最近點對在左側」、「最近點對在右側」、「最近點對橫跨兩側」等三種情形。先將左側與右側分別遞迴求解之後,再利用左側與右側的答案,快速的算出橫跨兩側的答案。

Preprocessing:
一、排序所有點,以X座標為主,Y座標無所謂。O(NlogN)
二、檢查是否有共點。如果有,就找出所有共點,演算法結束。O(N)

Divide:
把所有點分為左右兩側,左側、右側的點數盡量一樣多。

Conquer:
左側、右側分別遞迴求解。

Combine:
一、利用左側、右側的最佳解d,求出橫跨兩側的解:
 甲、首先找出靠近中線的點,水平距離小於d、包含d。O(N)
   (小於d、不包含d,則只找出其中一組最近點對。)
 乙、排序這些點,Y座標為主,X座標為輔。O(NlogN)
 丙、每一個點都找其上方鄰近的點,看看能不能形成最近點對。
   只需檢查至後三點。O(N*3) = O(N)
二、答案為左側、右側、橫跨兩側,三者當中的最佳解。

以下提供釋例。畫面上有一些點。

把點分為左側與右側,點數盡量一樣多。左側與右側的交界處可能會銜接,也可能不會銜接。左右兩側通常是不一樣寬的。

左側、右側分別遞迴求解,最後求得這兩種情況下的最近點對。最近點對的距離為 d 。

左側的每一個點,半徑 d 以內的範圍(不包含邊界),不會有其他左側的點存在,只可能出現另一側的點。右側亦如是。

要找出橫跨兩側的點對,可以從左側的右邊線,往左距離 d 以內的範圍裡(包含邊界)的這些點,有可能與右側的點形成最近點對。

也可以以右側的左邊線為主。

從左側的右邊線,往右距離 d 以內的範圍裡的這些點,則是可能的另一頭端點的範圍。

要找出橫跨兩側的最近點對,只要依序窮舉左側右邊界距離 d 以內、位於左側的點,作為左端點;再找左側右邊界距離 d 以內、位於右側的點,作為右端點。

從這裡開始衍生兩種實作方式:

一、最容易理解的方式,是從下往上掃描左端點;針對每個左端點,找到合適的右端點。右側之中,點與點之間的距離至少是 d 。運用先前的分析手法,我們只需檢查掃描線的中下兩點、上兩點,作為右端點,就能囊括所有橫跨兩側的最近點對。

此處省略分析過程,讀者可以自行畫圖觀察。

實作時,運用右側掃描線作為輔助,跟隨左側掃描線亦步亦趨,就能快速找到中下兩點、上兩點,而不必使用二分搜尋法。

二、另一個難以理解、但是容易實作的方式,是把範圍內的這些點全部混在一起,不分左右,然後從下往上掃描。先窮舉下端點,再尋找上方鄰近的點作為上端點,檢查是否形成最近點對。

最多只需要檢查下端點的後四點,就一定囊括所有橫跨兩側的最近點對。

此處省略分析過程,讀者可以自行畫圖觀察。蠻複雜的喔!可以先將左側、右側的分布情形分開畫好,再將左右兩側拼在一起。

更進一步。第四點一定與同側的另外一點形成最近點對,之後還是能檢查到,所以不必檢查第四點、只需要檢查後三點。

以上圖例都是掃描線掃中左側的點,讀者可以自行分析掃描線掃中右側的點的所有情況。大功告成。

教科書通常只談到後五點;此處更加深入分析,從後五點逼近至後三點。儘管推理過程讓人感覺似乎很有學問,但是執行速度仍舊不如窮舉法。這種鑽牛角尖又不切實際的學問,不如不學。

只找出最近點對的距離
  1. struct Point {double xy;} p[10], t[10];
  2. bool cmpx(const Pointiconst Pointj) {return i.x < j.x;}
  3. bool cmpy(const Pointiconst Pointj) {return i.y < j.y;}
  4.  
  5. double DnC(int Lint R)
  6. {
  7.     if (L >= Rreturn 1e9// 沒有點、只有一個點。
  8.     // 當剩下兩個點、三個點,
  9.     // 就可以直接求解,不必再遞迴下去、拖慢速度。
  10.  
  11.     /* Divide:把所有點分成左右兩側,點數盡量一樣多。 */
  12.  
  13.     int M = (L + R) / 2;
  14.  
  15.     /* Conquer:左側、右側分別遞迴求解。 */
  16.  
  17.     double d = min(DnC(L,M), DnC(M+1,R));
  18. //  if (d == 0.0) return d; // 提早結束
  19.  
  20.     /* Combine:尋找靠近中線的點,依照Y座標排序。O(NlogN)。 */
  21.  
  22.     int N = 0;  // 靠近中線的點數目
  23.     for (int i=M;   i>=L && p[M].x - p[i].x < d; --it[N++] = p[i];
  24.     for (int i=M+1i<=R && p[i].x - p[M].x < d; ++it[N++] = p[i];
  25.     sort(tt+Ncmpy); // O(NlogN)
  26.  
  27.     /* Combine:尋找橫跨兩側的最近點對。O(N)。 */
  28.  
  29.     for (int i=0i<N-1; ++i)
  30.         for (int j=1j<=3 && i+j<N; ++j)
  31.             d = min(ddistance(t[i], t[i+j]));
  32.  
  33.     return d;
  34. }
  35.  
  36. double closest_pair()
  37. {
  38.     sort(pp+10cmpx);
  39.     return DnC(0N-1);
  40. }

如果在 Combine 階段,以 Merge Sort 將所有點重新依照 Y 座標排序,時間複雜度可以降到 O(NlogN) 。然而執行 Merge Sort 的額外負擔實在太大,通常會比原來的方法慢上許多。

只找出最近點對的距離
  1. struct Point {double xy;} p[10], t[10];
  2. bool cmpx(const Pointiconst Pointj) {return i.x < j.x;}
  3. bool cmpy(const Pointiconst Pointj) {return i.y < j.y;}
  4.  
  5. double DnC(int Lint R)
  6. {
  7.     if (L >= Rreturn 1e9// 沒有點、只有一個點。
  8.  
  9.     /* Divide:把所有點分成左右兩側,點數盡量一樣多。 */
  10.  
  11.     int M = (L + R) / 2;
  12.  
  13.     // 先把中線的X座標記起來,因為待會重新排序之後會跑掉。
  14.     double x = p[M].x;
  15.  
  16.     /* Conquer:左側、右側分別遞迴求解。 */
  17.  
  18.     // 遞迴求解,並且依照Y座標重新排序。
  19.     double d = min(DnC(L,M), DnC(M+1,R));
  20. //  if (d == 0.0) return d; // 提早結束
  21.  
  22.     /* Combine:尋找靠近中線的點,依照Y座標排序。O(N)。 */
  23.  
  24.     // 尋找靠近中線的點,先找左側。各點已照Y座標排序了。
  25.     int N = 0;  // 靠近中線的點數目
  26.     for (int i=0i<=M; ++i)
  27.         if (x - p[i].x < d)
  28.             t[N++] = p[i];
  29.  
  30.     // 尋找靠近中線的點,再找右側。各點已照Y座標排序了。
  31.     int P = N;  // P為分隔位置
  32.     for (int i=M+1i<=R; ++i)
  33.         if (p[i].x - x < d)
  34.             t[N++] = p[i];
  35.  
  36.     // 以Y座標排序。使用Merge Sort方式,合併已排序的兩陣列。
  37.     inplace_merge(tt+Pt+Ncmpy);
  38.  
  39.     /* Merge:尋找橫跨兩側的最近點對。O(N)。 */
  40.  
  41.     for (int i=0i<N; ++i)
  42.         for (int j=1j<=3 && i+j<N; ++j)
  43.             d = min(ddistance(t[i], t[i+j]));
  44.  
  45.     /* Merge:重新以Y座標排序所有點。O(N)。 */
  46.  
  47.     // 如此一來,更大的子問題就可以直接使用Merge Sort。
  48.     inplace_merge(p+Lp+M+1p+R+1cmpy);
  49.  
  50.     return d;
  51. }
  52.  
  53. double closest_pair()
  54. {
  55.     sort(pp+10cmpx);
  56.     return DnC(0N-1);
  57. }

如果一開始將所有點複製一份,先以 Y 座標排序,那麼在遞迴途中就不用每次都排序。如此會使時間複雜度暴增為 O(N^2) ,甚至比窮舉法還慢。

只找出最近點對的距離
  1. struct Point {double xy;} px[10], py[10], t[10];
  2. bool cmpx(const Pointiconst Pointj) {return i.x < j.x;}
  3. bool cmpy(const Pointiconst Pointj) {return i.y < j.y;}
  4.  
  5. double DnC(int Lint R)
  6. {
  7.     if (L >= Rreturn 1e9;
  8.  
  9.     int M = (L + R) / 2;
  10.     double d = min(DnC(L,M), DnC(M+1,R));
  11. //  if (d == 0.0) return d; // 提早結束
  12.  
  13.     /* Merge:依照Y座標順序,尋找靠近中線的點。O(N)。 */
  14.  
  15.     int N = 0;  // 靠近中線的點數目
  16.     for (int i=0i<10; ++i)    // 全部的點都要找過一遍
  17.         if (py[i].x - px[M].x < d)
  18.             t[N++] = py[i];
  19.  
  20.     for (int i=0i<N-1; ++i)
  21.         for (int j=1j<=3 && i+j<N; ++j)
  22.             d = min(ddistance(t[i], t[i+j]));
  23.  
  24.     return d;
  25. }
  26.  
  27. double closest_pair()
  28. {
  29.     sort(pxpx+10cmpx);
  30.     copy(pxpx+10py);    // 先複製一份
  31.     sort(pypy+10cmpy);  // 然後依照Y座標排序
  32.     return DnC(0N-1);
  33. }

 

文章標籤
創作者介紹
創作者 pcorz 的頭像
pcorz

黑盒子部落格~電腦不難~資訊一把抓~

pcorz 發表在 痞客邦 留言(1) 人氣()


留言列表 (1)

發表留言
  • 俴 誏 ? 闚
  • 自將你向後我用們不孩大信家時隻在有把們真。

    消﹉費﹍日常用〇品就有◇返□利,﹎每﹂個月﹌幫﹉你打☆造﹌被動收入﹎
    go2l.ink/11Tz