Cod sursa(job #3302113)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 3 iulie 2025 14:24:49
Problema Cele mai apropiate puncte din plan Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.14 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fi first
#define sc second
#define pb push_back

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
template<typename type>
using ordered_set = tree<type, null_type, less<type>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 5, mod = 1e9 + 7, inf = 4e18;
const int dl[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
const int ddl[] = {-1, -1, -1, 0, 1, 1, 1, 0}, ddc[] = {-1, 0, 1, 1, 1, 0, -1, -1};

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int rng(int lo = 1, int hi = INT_MAX) {
    uniform_int_distribution<int> rnd(lo, hi);
    return rnd(gen);
}

struct mint {
    int val;
    mint(int32_t x = 0) {
        val = x % mod;
    }
    mint(long long x) {
        val = x % mod;
    }
    mint operator+(mint x) {
        return val + x.val;
    }
    mint operator-(mint x) {
        return val - x.val + mod;
    }
    mint operator*(mint x) {
        return 1LL * val * x.val;
    }
    void operator+=(mint x) {
        val = (*this + x).val;
    }
    void operator-=(mint x) {
        val = (*this - x).val;
    }
    void operator*=(mint x) {
        val = (*this * x).val;
    }
    friend auto operator>>(istream& in, mint &x) -> istream& {
        in >> x.val;
        x.val %= mod;
        return in;
    }
    friend auto operator<<(ostream& out, mint const &x) -> ostream& {
        out << x.val;
        return out;
    }
};

struct point {
    int x, y;
};

int n;
ll ans = inf;
pair<point, point> bst;
point v[N], aux[N];

bool comp(point x, point y) {
    return (x.y != y.y ? (x.y < y.y) : (x.x < y.x));
}
ll dist(point x, point y) {
    return (1ll * x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y);
}
void divide(int l, int r) {
    if(r - l + 1 <= 3) {
        for(int i=l; i<r; i++)
            for(int j=i+1; j<=r; j++)
                if(dist(v[i], v[j]) < ans) {
                    ans = dist(v[i], v[j]);
                    bst = {v[i], v[j]};
                }
        sort(v+l, v+r+1, comp);
    }
    else {
        int mid = (l + r) / 2;
        int midx = v[mid].x;
        divide(l, mid);
        divide(mid+1, r);

        merge(v+l, v+mid+1, v+mid+1, v+r+1, aux+1, comp);
        copy(aux+1, aux+(r-l+1)+1, v+l);

        int k = 0;
        for(int i=l; i<=r; i++)
            if(abs(v[i].x-midx) < ans)
                aux[++k] = v[i];
        for(int i=1; i<=k; i++)
            for(int j=i+1; j<=k && aux[j].y - aux[i].y < ans; j++)
                if(dist(aux[i], aux[j]) < ans) {
                    ans = dist(aux[i], aux[j]);
                    bst = {aux[i], aux[j]};
                }
    }
}

int32_t main() {
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(0);

    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> v[i].x >> v[i].y;
    sort(v+1, v+n+1, [&](point x, point y) {
        if(x.x != y.x)
            return x.x < y.x;
        else
            return x.y < y.y;
    });

    divide(1, n);
    
    cout << fixed << setprecision(6) << sqrt(ans);
    return 0;
}