Cod sursa(job #2837879)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 22 ianuarie 2022 20:20:06
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long int lli;

const int MAXN = 100000;

lli dist(pair<lli, lli> p1, pair<lli, lli> p2) {
	lli x1 = p1.first;
	lli y1 = p1.second;
	lli x2 = p2.first;
	lli y2 = p2.second;
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

int n;
pair<lli, lli> v[MAXN + 2];

lli calcMinDist(pair<lli, lli> v[], int le, int ri) {
	int nrEl = ri - le + 1;
	int mid = (le + ri) / 2;
	if (nrEl <= 3) {
		lli minDist = 9e18;
		for (int i = le; i <= ri; ++ i)
			for (int j = i + 1; j <= ri; ++ j)
				minDist = min(minDist, dist(v[i], v[j]));

		return minDist;
	} else {
		lli minDist = min(calcMinDist(v, le, mid), calcMinDist(v, mid + 1, ri));
		vector<pair<lli, lli> > m;
		lli d = (v[mid].first + v[mid + 1].first) / 2;

		for (int i = mid; i >= le && abs(d - v[i].first) <= minDist; -- i)
			m.push_back(make_pair(v[i].second, v[i].first));
		for (int i = mid + 1; i <= ri && abs(d - v[i].first) <= minDist; ++ i)
			m.push_back(make_pair(v[i].second, v[i].first));

		sort(m.begin(), m.end());

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

		return minDist;

	}
}

int main() {
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);

	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; ++ i) {
		cin >> v[i].first >> v[i].second;
	}

	sort(v, v + n);

	lli distSquared = calcMinDist(v, 0, n - 1);

	cout << fixed << setprecision(6) << sqrt(double(distSquared)) << '\n';

	return 0;
}