Cod sursa(job #2901073)

Utilizator a.stanciuStanciu Adrian a.stanciu Data 12 mai 2022 20:55:52
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#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;
}