Pagini recente » Cod sursa (job #987895) | Cod sursa (job #3340417) | Cod sursa (job #841006) | Cod sursa (job #680880) | Cod sursa (job #3339918)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <map>
#include <vector>
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];
map<pair<int, int>, vector<int>> mp;
int INF = (1LL << 60);
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;
}
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;
}