Pagini recente » Cod sursa (job #2998466) | Cod sursa (job #2056423) | Cod sursa (job #786708) | Cod sursa (job #305017) | Cod sursa (job #3228683)
#include <bits/stdc++.h>
long long sqr_dist(std::pair<int, int> a, std::pair<int, int> b) {
return ((long long)(a.first - b.first) * (a.first - b.first) +
(long long)(a.second - b.second) * (a.second - b.second));
}
int main() {
std::cin.tie(NULL);
std::iostream::sync_with_stdio(false);
#ifdef EVAL
std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
auto cinbuf = std::cin.rdbuf(fin.rdbuf());
auto coutbuf = std::cout.rdbuf(fout.rdbuf());
#endif
int n;
std::cin >> n;
std::map<std::pair<int, int>, std::vector<std::pair<int, int>>> quad;
long long min_dist_sqr = 1LL << 60;;
int min_dist = 1 << 30;
std::vector<std::pair<int, int> > points;
for (int i = 0; i < n; i++) {
std::pair<int, int> p;
std::cin >> p.first >> p.second;
p.first += 1000000000;
p.second += 1000000000;
std::pair<int, int> bucket = {p.first / min_dist, p.second / min_dist};
for (int dl = -1; dl <= 1; dl++)
for (int dc = -1; dc <= 1; dc++) {
std::pair<int, int> new_bucket = {bucket.first + dl, bucket.second + dc};
if (quad.find(new_bucket) == quad.end())
continue;
for (auto it: quad[new_bucket])
min_dist_sqr = std::min(min_dist_sqr, sqr_dist(it, p));
}
quad[bucket].push_back(p);
points.push_back(p);
int new_min_dist = (int)std::round(std::sqrt(min_dist_sqr));
if (new_min_dist < min_dist) {
min_dist = new_min_dist;
quad.clear();
for (auto it: points) {
bucket = {it.first / min_dist, it.second / min_dist};
quad[bucket].push_back(it);
}
}
}
std::cout << std::fixed << std::setprecision(10) << std::sqrt(min_dist_sqr);
return 0;
}