Cod sursa(job #3290482)

Utilizator _andr31Rusanescu Andrei-Marian _andr31 Data 30 martie 2025 20:11:13
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <limits.h>

using namespace std;
int n;

vector<pair<int, int>> points;

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

int bsearch1(vector<pair<int, int>>& v, int l, int r, double x) {
    int res = r;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (v[mid].first >= x) {
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

int bsearch2(vector<pair<int, int>>& v, int l, int r, double x) {
    int res = l;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (v[mid].first <= x) {
            l = mid + 1;
            res = mid;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

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

    int mid = l + (r - l) / 2;
    double left = divide(l, mid);
    double right = divide(mid + 1, r);
    double d = min(left, right);

    int leftest_left = bsearch1(points, l, mid, (double)points[mid].first - d);
    int rightest_right = bsearch2(points, mid + 1, r, (double)points[mid].first + d);

    sort(points.begin() + leftest_left, points.begin() + rightest_right + 1,
    [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second < b.second;
    });

    for (int i = leftest_left; i <= rightest_right; ++i) {
        for (int j = i + 1; j <= i + 7 && j <= rightest_right; ++j) {
            d = min(d, dist(points[i], points[j]));
        }
    }
    return d;
}

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

    points.resize(n);

    for (int i = 0; i < n; ++i) {
        fin >> points[i].first >> points[i].second;
    }

    sort(points.begin(), points.end(),
    [](const pair<int, int>& a, const pair<int, int>& b) {
        return a.first < b.first;
    });

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

    return 0;
}