Cod sursa(job #503458)

Utilizator freak93Adrian Budau freak93 Data 22 noiembrie 2010 22:40:16
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#define x first
#define y second

using namespace std;

const char iname[] = "cmap.in";
const char oname[] = "cmap.out";
const int maxn = 100002;
typedef long long ll;
const ll inf = 3e18;

ifstream f(iname);
ofstream g(oname);

pair<int, int> a[maxn], b[maxn], aux[maxn];
int i, j, n;

ll dis(pair<int, int> a, pair<int, int> b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

ll get(int begin, int end) {
	if (begin == end)
		return inf;
	if (end - begin == 1) {
		if (b[end] < b[begin])
			swap(b[begin], b[end]);
		return dis(b[begin], b[end]);
	}

	int mid = (begin + end) / 2;
	ll ans = min( get(begin, mid), get(mid + 1, end) );
    merge(b + begin, b + mid + 1, b + mid + 1, b + end + 1, aux);
	copy(aux, aux + (end - begin + 1), b + begin);
	int k = 0;
	for (int i = begin; i <= end; ++i)
		if ( abs(b[i].y - a[mid].x) <= ans)
			aux[k++] = b[i];
	for (int i = 0; i < k; ++i)
		for (int j = i + 1; j < k && j < i + 8; ++j)
			ans = min(ans, dis(aux[i], aux[j]));
	return ans;
}

int main() {
	f >> n;
	for (i = 1; i <= n; ++i)
		f >> a[i].x >> a[i].y;
	sort(a + 1, a + n + 1);
	for (i = 1; i <= n; ++i)
		b[i] = make_pair(a[i].y, a[i].x);

    g.setf(ios::fixed, ios::floatfield);
	g.precision(6);
	g << sqrt( get(1, n) ) << "\n";
}