# 題目: 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