Cod sursa(job #2279089)

Utilizator flibiaVisanu Cristian flibia Data 8 noiembrie 2018 21:49:30
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std; 

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

struct lol {
	ll x, y;
};

int n, vf;
lol a[100100], wek[100100];

ll dist(lol a, lol b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool cmp(lol a, lol b) {
	return a.x < b.x;
}

bool cmp2(lol a, lol b) {
	return a.y < b.y;
}

ll get(int st, int dr) {
	if (dr - st < 3) {
		ll ans = 2e9;
		for (int i = st; i < dr; i++)
			for (int j = i + 1; j <= dr; j++)
				ans = min(ans, dist(a[i], a[j]));
		return ans;
	}
	int mid = st + dr >> 1;
	ll bst = min(get(st, mid), get(mid, dr));
	vf = 0;
	for (int i = st; i <= dr; i++)
		if ((a[i].x - a[mid].x) * (a[i].x - a[mid].x) < bst)
			wek[++vf] = a[i];
	sort(wek + 1, wek + vf + 1, cmp2);
	for (int i =  1; i <= vf; i++)
		for (int j = 1; j <= vf && j - i < 8; j++)
			bst = min(bst, dist(wek[i], wek[j]));
	return bst;
}

int main() {
	in >> n;
	for (int i = 1; i <= n; i++)
		in >> a[i].x >> a[i].y;
	sort(a + 1, a + n + 1, cmp);
	out << fixed << setprecision(6) << sqrt((double) get(1, n));
	return 0;
}