Pagini recente » Cod sursa (job #884836) | Cod sursa (job #2609599) | Cod sursa (job #1392682) | Cod sursa (job #2915077) | Cod sursa (job #3228688)
#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 INFOARENA
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) + 1;
std::vector<std::pair<int, int> > points(n);
for (int i = 0; i < n; i++) {
std::cin >> points[i].first >> points[i].second;
points[i].first += 1000000000;
points[i].second += 1000000000;
}
std::mt19937 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::shuffle(points.begin(), points.end(), rng);
for (int i = 0; i < n; i++) {
std::pair<int, int> p = points[i];
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);
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 (int j = 0; j <= i; j++) {
std::pair<int, int> it = points[j];
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;
}