Pagini recente » Monitorul de evaluare | Cod sursa (job #3327242) | Cod sursa (job #2658802) | Cod sursa (job #1552310) | Cod sursa (job #3339936)
//solutie misto cu sqrt :))
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct pair_hash
{
inline size_t operator()(const pair<int, int> &a) const {
int x = a.first;
int y = a.second;
return (x * 31337) ^ (y * 1000000007);
}
};
ifstream in("cmap.in");
ofstream out("cmap.out");
int n, d;
pair<int, int> v[100005];
unordered_map<pair<int, int>, vector<int>, pair_hash> mp;
int INF = (1LL << 60);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dist(pair<int, int> a, pair<int, int> b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
void insert_point(int i)
{
int x = v[i].first / d;
int y = v[i].second / d;
mp[{x, y}].push_back(i);
}
signed main()
{
in>>n;
for(int i = 1; i<=n; i++)
{
in>>v[i].first>>v[i].second;
}
shuffle(v + 1, v + n + 1, rng);
d = sqrt(dist(v[1], v[2]));
int ans = dist(v[1], v[2]);
insert_point(1);
insert_point(2);
for(int i = 3; i<=n; i++)
{
int x = v[i].first / d;
int y = v[i].second / d;
int updated = 0;
for(int dx = -1; dx<=1; dx++)
{
for(int dy = -1; dy<=1; dy++)
{
pair<int, int> key = {x + dx, y + dy};
if(mp.find(key) != mp.end())
{
for(auto it: mp[key])
{
int cur_d = dist(v[i], v[it]);
if(cur_d < ans)
{
ans = cur_d;
updated = 1;
}
}
}
}
}
if(updated == 1)
{
d = sqrt(ans);
mp.clear();
for(int j = 1; j<i; j++)
{
insert_point(j);
}
}
insert_point(i);
}
long double rez = sqrt(ans);
out<<setprecision(6)<<fixed<<rez;
return 0;
}