Cod sursa(job #3290450)

Utilizator ancamaximMaxim Anca Stefania ancamaxim Data 30 martie 2025 18:58:19
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> p;

double sq(double x) {
    return x * x;
}

double dist(pair<int, int> a, pair<int, int> b) {
    return sqrt(sq(((double)(a.first - b.first))) + sq(((double)(a.second - b.second))));
}

int smallest_bigger(int l, int r, double x) {
    int res = l;

    while(l <= r) {
        int mid = (r - l) / 2 + l;

        if ((double) p[mid].first >= x) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

int biggest_smaller(int l, int r, double x) {
    int res = r;

    while(l <= r) {
        int mid = (r - l) / 2 + l;

        if ((double) p[mid].first <= x) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

double divide(int l, int r)
{
    if (r == l)
        return INT_MAX;
    if (r == l + 1)
        return dist(p[l], p[r]);

    int mid = (r - l) / 2 + l;
    double d1 = divide(l, mid);
    double d2 = divide(mid + 1, r);
    double d = min(d1, d2);
    
    // cautam cel mai mic nr > p[mid] - d
    int p1 = smallest_bigger(l, mid, (double)p[mid].first - d);
    // cautam cel mai mare nr < p[mid] + d
    int p2 = biggest_smaller(mid + 1, r, (double)p[mid].first + d);

    // sortare dupa y
    auto comp = [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    };
    sort(p.begin() + p1, p.begin() + p2 + 1, comp);
    for (int i = p1; i <= p2; ++i) {
        for (int j = 1; j <= 6 && j + i <= p2; ++j)
            d = min(d, dist(p[i], p[i + j]));
    }
    return d;
}

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

    fin >> n;
    p.resize(n);
    for (int i = 0; i < n; ++i)
        fin >> p[i].first >> p[i].second;

    auto comp = [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.first == b.first ? a.second < b.second : a.first < b.first;
    };
    sort(p.begin(), p.end(), comp);

    fout << fixed << setprecision(6) << divide(0, n - 1);
}