Cod sursa(job #2278851)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 8 noiembrie 2018 17:14:25
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 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], b[100100];

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

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

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

	{ // merge
		vector < PII > V;
		int p1 = st, p2 = mid + 1, p = 0;
		while (p1 <= mid && p2 <= dr) {
			if (b[p1].y < b[p2].y) V.push_back(b[p1++]);
			else V.push_back(b[p2++]);
		}

		while (p1 <= mid) V.push_back(b[p1++]);
		while (p2 <= dr) V.push_back(b[p2++]);

		for (int i = st; i <= dr; i++) b[i] = V[p++];
	}

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

	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;
		b[i] = {a[i].y, a[i].x};
	}

	sort(a + 1, a + n + 1);

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

	return 0;
}