Cod sursa(job #3234089)

Utilizator betybety bety bety Data 6 iunie 2024 11:32:40
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
using pii = pair<int, int>;
using ld = long double;
const ld inf = 1e9;
const int lim = 1e5 + 4;
pii v[lim];
int n;
bool bySecond(pii a, pii b) {
	if (a.second == b.second) {
		return a.first < b.first;
	}
	return a.second < b.second;
}
ld dist(pii a, pii b) {
	return sqrt(1. * (a.first - b.first) * (a.first - b.first) +
				1. * (a.second - b.second) * (a.second - b.second));
}
ld solve(int l, int r) {
	if (l >= r) {
		return inf;
	}
	int med = (l + r) >> 1;
	int line = v[med].first;
	ld d = min(solve(l, med), solve(med + 1, r));
	vector<pii> manual;
	for (int i = l; i <= r; ++i) {
		if (v[i].first >= line - d and v[i].first <= line + d) {
			manual.push_back(v[i]);
		}
	}
	sort(manual.begin(), manual.end(), bySecond);
	int lefty = 0;
	ld ans = d;
	for (int c = 0; c < manual.size(); ++c) {
		pii p = manual[c];
		while (manual[lefty].second < p.second - d) {
			++lefty;
		}
		for (int i = lefty; i < c; ++i) {
			ans = min(ans, dist(manual[i], p));
		}
	}
	return ans;
}
int main() {
	in >> n;
	for (int i = 1; i <= n; ++i) {
		in >> v[i].first >> v[i].second;
	}
	sort(v + 1, v + n + 1);
	out << fixed << setprecision(9) << solve(1, n) << '\n';
	return 0;
}