Cod sursa(job #3235092)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 13 iunie 2024 23:17:23
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.38 kb
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const string OUT[2]{ "NO", "YES" };
const string out[2]{ "No", "Yes" };
#define all(a) a.begin(), a.end()
#define OK() cerr << "OK until line " << __LINE__ << nl
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ifstream fin("cmap.in");
ofstream fout("cmap.out");

auto start_time = chrono::high_resolution_clock::now();

double getTime() {
    auto end_time = chrono::high_resolution_clock::now();
    return chrono::duration<double>(end_time - start_time).count();
}

template<typename T>
int rand(T a, T b) { return uniform_int_distribution<T>(a, b)(rng); }

template<typename T1, typename T2>
bool ckmax(T1& a, T2 b) { return a < b ? a = b, true : false; }

template<typename T1, typename T2>
bool ckmin(T1& a, T2 b) { return a > b ? a = b, true : false; }

struct point {
    int x, y;
    int index;
    point() {
        x = y = 0;
    }
    point(int x, int y) {
        this->x = x;
        this->y = y;
    }
    bool operator<(const point& other) {
        return x == other.x ? y < other.y : x < other.x;
    }
    friend double distance(const point& lhs, const point& rhs) {
        return sqrt(pow(lhs.x - rhs.x, 2) + pow(lhs.y - rhs.y, 2));
    }
};

const int nmax = 5e4;
int n;
point p[nmax + 5];
double min_dist = 1e18;
pair<int, int> best;
point aux[nmax + 5];

struct compare_y {
    bool operator()(const point& a, const point& b) {
        return a.y < b.y;
    }
};

void find_closest_points(int l, int r) {
    // bruteforce for small amount of points
    if (r - l + 1 <= 3) {
        for (int i = l; i <= r; ++i) {
            for (int j = i + 1; j <= r; ++j) {
                if (ckmin(min_dist, distance(p[i], p[j]))) {
                    best = make_pair(p[i].index, p[j].index);
                }
            }
        }
        // sortam dupa y
        sort(p + l, p + r + 1, compare_y());
        return;
    }
    int mid = (l + r) / 2;
    // vedem dreapta despartitoare inainte deoarece ordinea punctelor va fi modificata ulterior
    int midx = p[mid].x;
    // cautam in stanga si in dreapta distanta minima
    find_closest_points(l, mid);
    find_closest_points(mid + 1, r);
    // mergesort -> le avem sortate dupa y (decat sa le sortam din nou)
    merge(p + l, p + mid + 1, p + mid + 1, p + r + 1, aux + 1, compare_y());
    copy(aux + 1, aux + (r - l + 1) + 1, p + l);
    int k = 0;
    // cautam punctele din jurul dreptei
    for (int i = l; i <= r; ++i) {
        if (abs(p[i].x - midx) < min_dist) {
            aux[++k] = p[i];
        }
    }
    // vedem daca putem gasi 2 puncte mai apropiate de distanta minima curenta
    for (int i = 1; i <= k; ++i) {
        for (int j = i + 1; j <= k && aux[j].y - aux[i].y < min_dist; ++j) {
            if (ckmin(min_dist, distance(aux[i], aux[j]))) {
                best = make_pair(aux[i].index, aux[j].index);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> p[i].x >> p[i].y;
        p[i].index = i;
    }
    sort(p + 1, p + n + 1);
    find_closest_points(1, n);
    fout << fixed << setprecision(6) << min_dist;
}