Cod sursa(job #2278865)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 8 noiembrie 2018 17:30:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define MOD 1000000007
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair< int , int > PII;

int n, m, cnt;
PII a[100100];

double dist(PII a, PII b) {
	return sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}

double divide(int st, int dr) {
	if (dr - st <= 2) {
		double d = 1e18;
		for (int i = st; i < dr; i++){
			for (int j = i + 1; j <= dr; j++){
				d = min(d, dist(a[i], a[j]));
			}
		}
		return d;
	}

	int mid = (st + dr) >> 1;
	double d = min(divide(st, mid), divide(mid + 1, dr));

	vector < PII > V;
	for (int i = st; i <= dr; i++) {
		if (abs(a[i].x - a[mid].x) < d) V.push_back(a[i]);
	}

	sort(V.begin(), V.end(), [&](PII a, PII b){ return a.y > b.y; });

	for (int i = 0; i < V.size(); i++)
		for (int j = i + 1; j < V.size() && j - i <= 7; j++)
			d = min(d, dist(V[i], V[j]));

	return d;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

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

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y;
	}

	sort(a + 1, a + n + 1);
	cout << setprecision(6) << fixed << divide(1, n);

	return 0;
}