Cod sursa(job #3225800)

Utilizator alexdumitruAlexandru Dumitru alexdumitru Data 18 aprilie 2024 21:14:13
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

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

const int NMAX = 1e5;

int n;
pair<int, int> a[NMAX + 1];

ll dist(pair<int, int> a, pair<int, int> b) {
    return 1LL * (a.first - b.first) * (a.first - b.first) + 1LL * (a.second - b.second) * (a.second - b.second);
}

bool cmpX(const pair<int, int> & a, const pair<int, int> & b) {
    return a.first < b.first;
}

bool cmpY(const pair<int, int> & a, const pair<int, int> & b) {
    return a.second < b.second;
}

ll ans;

void go(int st, int dr) {
    if (st >= dr)
        return;

    if (dr == st + 1) {
        ans = min(ans, dist(a[st], a[dr]));
        return;
    }

    int mij = (st + dr) / 2;
    go(st, mij);
    go(mij + 1, dr);

    vector<pair<int, int>> v;

    for (int i = st; i <= dr; i++)
        if (1LL * (a[i].first - a[mij].first) * (a[i].first - a[mij].first) < ans)
            v.push_back(a[i]);

    sort(v.begin(), v.end(), cmpY);

    for (int i = 0; i < v.size(); i++) {
        for (int j = i + 1; j < v.size(); j++) {
            if (1LL * (v[j].second - v[i].second) * (v[j].second - v[i].second) >= ans)
                break;
            ans = min(ans, dist(v[i], v[j]));
        }
    }
}

void solve() {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i].first >> a[i].second;

    sort(a + 1, a + n + 1, cmpX);

    ans = dist(a[1], a[2]);

    go(1, n);

    ld Ans = (ld)sqrt((ld)ans);

    fout << fixed << setprecision(6) << Ans << '\n';
}

signed main() {
    solve();
    return 0;
}