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