Cod sursa(job #1025645)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 10 noiembrie 2013 13:35:42
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <utility>

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

const int MaxArraySize = 100001;
const long long Inf = 1LL << 61

long long n, ans;
pair<long long, long long> vec[MaxArraySize], x[MaxArraySize], y[MaxArraySize];

long long dist(pair<long long, long long> a, pair<long long, long long> b) {
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

long long modul(long long val) {
	if (val < 0)
		return -val;
	return val;
}

long long dive_et_imp(int st, int dr, pair<long long, long long> x[], pair<long long, long long> y[]) {

	if (st >= dr - 1)
		return Inf;

	if (dr - st == 2) {
		if (y[st] > y[st + 1])
			swap(y[st], y[st + 1]);
		return dist(x[st], x[st + 1]);
	}

	long long sol, mij, i, j, m = 0;

	mij = st + (dr - st) / 2;
	sol = min(dive_et_imp(st, mij, x, y), dive_et_imp(mij, dr, x, y));

	sort(y + st, y + dr);

	for (i = st; i < dr; ++i)
		if (sol >= modul(y[i].second - x[mij].first))
			vec[m++] = y[i];

	for (i = 0; i < m - 1; ++i) {
		for (j = i + 1; j < m && j - i < 8; ++j)
			sol = min(sol, dist(vec[i], vec[j]));
	}

	return sol;
}

int main() {

	int i;

	f >> n;

	for (i = 0; i < n; ++i)
		f >> x[i].first >> x[i].second;

	sort(x, x + n);

	for (i = 0; i < n; ++i)
		y[i] = make_pair(x[i].second, x[i].first);

	ans = dive_et_imp(0, n, x, y);

	g << fixed << setprecision(6) << sqrt(ans) << "\n";

	f.close();
	g.close();

	return 0;
}