Cod sursa(job #2710731)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 22 februarie 2021 22:25:47
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;
typedef long double ld;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l, int r)
{
	return uniform_int_distribution<int>(l, r)(rng);
}

ld between(pi a, pi b)
{
	return sqrt(1ll*(a.first-b.first)*(a.first-b.first) + 1ll*(a.second-b.second)*(a.second-b.second));
}

ld dist = 0;
ld truemin = 0;

int toInt(ld x)
{
	int y = x;
	return max(y, 1);
}

int hash2(pi p, int addx = 0, int addy = 0)
{
	p.first /= toInt(dist);
	p.second /= toInt(dist);
	p.first += addx;
	p.second += addy;
	return p.first^p.second;
}

vector<int> fastSolver(vector<pi> r)
{
	int n = r.size();
	vector<pi> v;
	vector<int> ans;
	unordered_map<int, vector<pi>> mp;
	for (int i = 0; i < n; ++i) {
		pi now = r[i];
		v.push_back(now);
		if (i == 0)
			continue;
		if (i == 1) {
			dist = between(v[0], v[1]);
			truemin = between(v[0], v[1]);
			ans.push_back(truemin);
			mp[hash2(v[0])].push_back(v[0]);
			mp[hash2(v[1])].push_back(v[1]);
			continue;
		}
		ld newmin = dist;
		for (int a = -1; a <= 1; ++a)
			for (int b = -1; b <= 1; ++b)
				for (auto point : mp[hash2(now, a, b)])
					newmin = min(newmin, between(now, point));
		mp[hash2(now)].push_back(now);
		truemin = min(truemin, newmin);
		ans.push_back(truemin);
		if (truemin*2 < dist) {
			dist = truemin;
			mp.clear();
			for (auto x : v)
				mp[hash2(x)].push_back(x);
		
		}
	}
	return ans;
}

vector<int> slowSolver(vector<pi> r)
{
	int n = r.size();
	truemin = between(r[0], r[1]);
	vector<int> ans;
	ans.push_back(truemin);
	for (int i = 2; i < n; ++i) {
		for (int j = 0; j < i; ++j)
			truemin = min(truemin, between(r[i], r[j]));
		ans.push_back(truemin);
	}
	return ans;
}

int main()
{
	int n;
	cin >> n;
	vector<pi> v(n);
	for (int i = 0; i < n; ++i)
		cin >> v[i].first >> v[i].second;
	fastSolver(v);
	cout << truemin << "\n";
	return 0;
}