Pagini recente » Cod sursa (job #1983285) | Cod sursa (job #3123694) | Cod sursa (job #915913) | Cod sursa (job #3283201) | Cod sursa (job #2710732)
#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()
{
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
int n;
fin >> n;
vector<pi> v(n);
for (int i = 0; i < n; ++i)
fin >> v[i].first >> v[i].second;
fastSolver(v);
fout << truemin << "\n";
return 0;
}