# 題目: UVa 10245 - The Closest Pair Problem
# 題目說明
給 N
個點 (x, y 平面座標),求這些點的最近距離
INPUT:
每筆測資輸入一個整數 N
接下來有 N
行,每行輸入兩個變數,為點的 x, y 座標
OUTPUT:
輸出這些點的最近距離,如果 >= 10000
則輸出 INFINITY
# 解題方法
針對 x
做排序後,利用 Divide and Conquer
持續將所有點切成兩半
直到找到左半邊的最小值 l
、右半邊的最小值 r
將 d
設為 min(l ,r)
,在 中線 - d ~ 中線 + d
的範圍內尋找更小的值
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <math.h> | |
#include <iomanip> | |
using namespace std; | |
struct point | |
{ | |
double x; | |
double y; | |
}; | |
int N; | |
double dis; | |
vector<point> V; | |
static auto fast_io = [] | |
{ | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
return 0; | |
}(); | |
void read() | |
{ | |
double a, b; | |
V.clear(); | |
for (int i = 0; i < N; ++i) cin >> a >> b, V.push_back({ a, b }); | |
} | |
double ds(point& a, point& b) | |
{ | |
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); | |
} | |
double Combine(int& a, int& b, int& mid, double& l, double& r) | |
{ | |
double d = min(l, r); | |
double line = (V[mid].x + V[mid + 1].x) / 2; | |
double Min = d; | |
for (int i = mid + 1; i <= b && V[i].x < line + d; ++i) | |
for (int j = mid; j >= a && V[j].x > line - d; --j) | |
Min = min(Min, ds(V[i], V[j])); | |
return Min; | |
} | |
double Divide(int a, int b) | |
{ | |
if (a >= b) return 10000; | |
int mid = (a + b) / 2; | |
double l = Divide(a, mid); | |
double r = Divide(mid + 1, b); | |
return Combine(a, b, mid, l, r); | |
} | |
void print() | |
{ | |
if (dis < 10000) cout << setprecision(4) << fixed << dis << "\n"; | |
else cout << "INFINITY\n"; | |
} | |
int main() | |
{ | |
while (cin >> N, N) | |
{ | |
read(); | |
sort(V.begin(), V.end(), [](point& a, point& b) { return a.x < b.x; }); | |
dis = Divide(0, N - 1); | |
print(); | |
} | |
} |
# 參考資料
http://programming-study-notes.blogspot.com/2014/01/uva-10245-closest-pair-problem.html