Cod sursa(job #3154854)

Utilizator rastervcrastervc rastervc Data 6 octombrie 2023 16:37:45
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <bits/stdc++.h>

using namespace std;

struct Point {
    double x, y;
    Point() : x(), y() {}
    Point(double x, double y) : x(x), y(y) {}
};

using PointPair = pair<Point, Point>;

const PointPair INF = { Point(-1e9, 1e9), Point(1e9, 1e9) };

double dist(const PointPair &points) {
    const double d1 = points.second.x - points.first.x;
    const double d2 = points.second.y - points.first.y;
    return sqrt(d1 * d1 + d2 * d2);
}

PointPair closest_pair_two(const PointPair &pair1, const PointPair &pair2) {
    return dist(pair1) < dist(pair2) ? pair1 : pair2;
}

PointPair strip_closest_pair(const vector<Point> &points) {
    PointPair ans = { points[0], points[1] };
    for (int i = 0; i < (int)points.size(); ++i)
        for (int j = i + 1; j < (int)points.size() && j - i < 9; ++j)
            ans = closest_pair_two(ans, { points[i], points[j] });
    return ans;
}

PointPair divide_and_conquer(const vector<Point> &points, int l, int r) {
    if (l == r) return INF;
    const int mid = (l + r) >> 1;

    PointPair ans_left = divide_and_conquer(points, l, mid);
    PointPair ans_right = divide_and_conquer(points, mid + 1, r);
    PointPair ans = closest_pair_two(ans_left, ans_right);
    const double delta = dist(ans);
    
    vector<Point> strip;
    for (int i = l; i < r; ++i)
        if (abs(points[i].x - points[mid].x) <= delta)
            strip.push_back(points[i]);

    sort(strip.begin(), strip.end(), [](Point P1, Point P2) {
        return P1.y < P2.y || (P1.y == P2.y && P1.x < P2.x);
    });

    return closest_pair_two(ans, strip_closest_pair(strip));
}

PointPair closest_pair(vector<Point> &points) {
    sort(points.begin(), points.end(), [](Point P1, Point P2) {
        return P1.x < P2.x || (P1.x == P2.x && P1.y < P2.y);
    });
    return divide_and_conquer(points, 0, points.size());
}

int main() {
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");

    int N;
    fin >> N;

    vector<Point> points(N);
    for (Point &point : points)
        fin >> point.x >> point.y;

    fout << fixed << setprecision(8) << dist(closest_pair(points));

    fin.close();
    fout.close();
    return 0;
}