Pagini recente » Cod sursa (job #759058) | Cod sursa (job #594376) | Cod sursa (job #2739330) | Cod sursa (job #2575952) | Cod sursa (job #2417637)
#include <bits/stdc++.h>
#define llg long long
#define int_pair std::pair <int, int>
std::istream& operator >> (std::istream& stream, int_pair& data) {
return stream >> data.first >> data.second;
}
std::set <int_pair> set;
llg closestPair (std::vector <int_pair>& pts) {
std::sort(pts.begin(), pts.end());
llg dist2 = (1LL<<61);
for (int i=0, idx=0; i<pts.size(); ++i) {
int dist = ceil(sqrt(dist2));
while (pts[i].first - pts[idx].first >= dist2)
set.erase({pts[idx].second, pts[idx++].first});
auto it1 = set.lower_bound({pts[i].second-dist, pts[i].first});
auto it2 = set.upper_bound({pts[i].second+dist, pts[i].first});
int x, y;
for (auto it = it1; it != it2; ++ it)
x = pts[i].first - it->second, y = pts[i].second - it->first,
dist2 = std::min(dist2, 1LL*x*x + 1LL*y*y);
set.insert({pts[i].second, pts[i].first});
} return dist2;
}
int N;
std::vector <int_pair> V;
std::ifstream input ("cmap.in");
std::ofstream output("cmap.out");
void readInput() {
input >> N;
V.resize(N);
for (auto &it:V)
input >> it;
}
void solveInput() {
output << std::fixed << std::setprecision(6) << sqrt(double(closestPair(V))) << '\n';
}
int main()
{
readInput();
solveInput();
return 0;
}