Cod sursa(job #3258076)

Utilizator Mihai_OctMihai Octavian Mihai_Oct Data 20 noiembrie 2024 19:09:02
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Punct {
    long long x, y;

    Punct(long long _x = 0, long long _y = 0) {
        x = _x;
        y = _y;
    }

    long long LungTo(Punct p) {
        return (p.x - x) * (p.x - x) + (p.y - y) * (p.y - y);
    }

    double Dist(Punct p) {
        return sqrt(LungTo(p));
    }
};
Punct p[100002];
long long n, i;

static inline bool CmpX(Punct p1, Punct p2) {
    return p1.x < p2.x;
}

static inline bool CmpY(Punct p1, Punct p2) {
    return p1.y < p2.y;
}

static inline long long Divi(long long st, long long dr) {
    if(st == dr) return INT_MAX;

    long long mij = st + (dr - st) / 2;
    long long rst = Divi(st, mij);
    long long rdr = Divi(mij + 1, dr);
    long long r = min(rst, rdr);

    vector<Punct> v;
    for(int i = st; i <= dr; i++) v.push_back(p[i]);

    sort(v.begin(), v.end(), CmpY);
    for(int i = 0; i < v.size() - 1; i++) {
        for(int j = i + 1; j < v.size(); j++) {
            if(v[i].LungTo(v[j]) > r) break;
            r = min(r, v[i].LungTo(v[j]));
        }
    }
    return r;
}

int main()  {
    fin >> n;
    for(i = 1; i <= n; i++) fin >> p[i].x >> p[i].y;

    sort(p + 1, p + n + 1, CmpX);

    fout << fixed << setprecision(12) << sqrt(Divi(1, n));

    return 0;
}