Cod sursa(job #2482922)

Utilizator gabrielmGabriel Majeri gabrielm Data 29 octombrie 2019 08:18:29
Problema Cele mai apropiate puncte din plan Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.45 kb
#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y;
};

istream& operator>>(istream& is, Point& pt) {
    return is >> pt.x >> pt.y;
}

ostream& operator<<(ostream& os, const Point& pt) {
    return os << "(" << pt.x << ", " << pt.y << ")";
}

double distance(Point a, Point b) {
    double dx = double(a.x) - double(b.x),
           dy = double(a.y) - double(b.y);
    return sqrt(dx * dx + dy * dy);
}

double min_distance(size_t num_pts, const Point* xs, const Point* ys) {
    if (num_pts <= 1) {
        return INFINITY;
    }
    if (num_pts == 2) {
        return distance(xs[0], xs[1]);
    }
    if (num_pts == 3) {
        double a = distance(xs[0], xs[1]),
               b = distance(xs[0], xs[2]),
               c = distance(xs[1], xs[2]);
        return min(a, min(b, c));
    }

    int mid = num_pts / 2;
    int mid_x = xs[mid].x;

    const Point* left_xs = xs;
    const Point* right_xs = xs + mid;
    vector<Point> left_ys, right_ys;
    left_ys.reserve(mid);
    right_ys.reserve(mid);

    for (size_t i = 0; i < num_pts; ++i) {
        if (ys[i].x < mid_x) {
            left_ys.push_back(ys[i]);
        } else {
            right_ys.push_back(ys[i]);
        }
    }

    double min_left = min_distance(mid, left_xs, left_ys.data()),
           min_right = min_distance(mid, right_xs, right_ys.data());

    double d = min(min_left, min_right);

    vector<Point> closer;
    closer.reserve(num_pts);
    for (size_t i = 0; i < num_pts; ++i) {
        double dx = double(ys[i].x) - double(mid_x);
        if (dx * dx <= d * d) {
            closer.push_back(ys[i]);
        }
    }

    if (closer.size() > 0) {
        size_t i = 0;
        while (i < closer.size() - 1) {
            size_t j = i + 1;
            while (j < closer.size() && (j - i) <= 16) {
                d = min(d, distance(closer[i], closer[j]));
                ++j;
            }
            ++i;
        }
    }

    return d;
}

int main() {
    ifstream in("cmap.in");

    size_t num_pts;
    in >> num_pts;

    vector<Point> pts(num_pts);
    for (size_t i = 0; i < num_pts; ++i) {
        in >> pts[i];
    }

    vector<Point> xs = pts, ys = pts;

    sort(xs.begin(), xs.end(), [] (const Point& a, const Point& b) { return a.x < b.x; });
    sort(ys.begin(), ys.end(), [] (const Point& a, const Point& b) { return a.y < b.y; });

    ofstream out("cmap.out");
    double d = min_distance(num_pts, xs.data(), ys.data());
    out << setprecision(6) << fixed << d << '\n';
}