Cod sursa(job #3323916)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 20 noiembrie 2025 13:10:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Punct {
    long long x, y;
};
Punct v[102], vv[102];
long long n, i;

static inline long long Dist(Punct a, Punct b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

static inline bool Cmp(Punct a, Punct b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

static inline int DEI(int st, int dr) {
    cout << st << " " << dr << "\n";

    if(dr - st < 1) return LLONG_MAX;
    else if(dr - st == 1) {
        if(!Cmp(vv[st], vv[st + 1])) swap(vv[st], vv[st + 1]);
        return Dist(v[st], v[st + 1]);
    }

    long long mij = st + (dr - st) / 2;
    long long rasp = min(DEI(st, mij), DEI(mij + 1, dr));

    sort(vv + st, vv + dr + 1, Cmp);

    vector<Punct> sel;
    for(long long i = st; i <= dr; i++) {
        if(abs(vv[i].y - v[mij].x) <= rasp) sel.push_back(vv[i]);
    }

    for(long long i = 0; i < sel.size() - 1; i++) {
        for(long long j = i + 1; j < sel.size() && j - i < 8; j++) {
            rasp = min(rasp, Dist(sel[i], sel[j]));
        }
    }
    return rasp;
}

int main() {
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n;
    for(i = 1; i <= n; i++) fin >> v[i].x >> v[i].y;
    sort(v + 1, v + n + 1, Cmp);
    for(i = 1; i <= n; i++) vv[i] = {v[i].y, v[i].x};

    fout << setprecision(6) << fixed << sqrt(DEI(1, n)) << "\n";

    return 0;
}