Cod sursa(job #2264039)

Utilizator flibiaVisanu Cristian flibia Data 19 octombrie 2018 19:15:56
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define ll long long 
#define ld long double
#define fi first
#define se second

using namespace std;

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

int n, vf;
pair <ll, ll> a[100100], L, wek[100100];

ll dist(const pair <ll, ll> &a, const pair <ll, ll> &b) {
	return (a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se);
}

bool cmp(const pair <ll, ll> &a, const pair <ll, ll> &b) {
	return a.se < b.se;
}

ll solve(int st, int dr) {
	if (dr - st + 1 <= 3) {
		ll bst = LLONG_MAX;
		for (int i = st; i < dr; i++)
			for (int j = i + 1; j <= dr; j++)
				bst = min(bst, dist(a[i], a[j]));
		return bst;
	}
	int mid = st + dr >> 1;
	ll bst = min(solve(st, mid), solve(mid + 1, dr));
	ll v = (a[mid].fi + a[mid + 1].fi) / 2LL;
	vf = 0;
	for (int i = st; i <= mid; i++)
		if ((a[i].fi - v) * (a[i].fi - v) <= bst + 1)
			wek[++vf] = a[i];
	sort(wek + 1, wek + vf + 1, cmp);
	for (int i = 1; i <= vf; i++)
		for (int j = i + 1; j <= vf && j - i <= 7; j++)
			bst = min(bst, dist(wek[i], wek[j]));
	return bst;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	in >> n;
	for (int i = 1; i <= n; i++)
		in >> a[i].fi >> a[i].se;
	sort(a + 1, a + n + 1);
	out << fixed << setprecision(6) << sqrt((ld) solve(1, n));
	return 0;
}