Pagini recente » Cod sursa (job #2437604) | Cod sursa (job #720075) | Cod sursa (job #2830886) | Cod sursa (job #2415977) | Cod sursa (job #2901073)
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x;
int y;
Point(int x, int y) : x(x), y(y) {}
};
auto squared_dist(const Point& from, const Point& to)
{
auto dx = from.x - to.x;
auto dy = from.y - to.y;
return 1l * dx * dx + 1l * dy * dy;
}
auto solve(int n, vector<Point>& points)
{
sort(points.begin(), points.end(), [] (const auto& lhs, const auto& rhs) {
return tie(lhs.x, lhs.y) < tie(rhs.x, rhs.y);
});
auto min_d = squared_dist(points[0], points[1]);
queue<int> q;
set<pair<long, int>> y_set;
for (auto i = 0; i < n; ++i) {
auto dy = static_cast<long>(ceil(sqrt(min_d)));
auto b_it = y_set.lower_bound(make_pair(points[i].y - dy, -1));
auto e_it = y_set.upper_bound(make_pair(points[i].y + dy, n));
for (auto it = b_it; it != e_it; ++it)
min_d = min(min_d, squared_dist(points[i], points[it->second]));
while (!q.empty()) {
auto idx = q.front();
auto dx = points[i].x - points[idx].x;
if (1l * dx * dx <= min_d)
break;
q.pop();
y_set.erase(make_pair(points[idx].y, idx));
}
q.push(i);
y_set.insert(make_pair(points[i].y, i));
}
return min_d;
}
int main()
{
FILE *in = fopen("cmap.in", "r");
FILE *out = fopen("cmap.out", "w");
if (!in || !out)
return -1;
int n;
fscanf(in, "%d", &n);
vector<Point> points;
points.reserve(n);
for (auto i = 0; i < n; ++i) {
int x, y;
fscanf(in, "%d %d", &x, &y);
points.emplace_back(x, y);
}
fprintf(out, "%lf\n", sqrt(solve(n, points)));
fclose(in);
fclose(out);
return 0;
}