Cod sursa(job #2472544)

Utilizator LucaSeriSeritan Luca LucaSeri Data 12 octombrie 2019 16:12:37
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.19 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")

using namespace __gnu_pbds;
using namespace std;
     
#define mp make_pair
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define eb emplace_back
 
typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef unsigned long long ull;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vll;
typedef vector< vll > vvll;
typedef vector< pii > vpii;
typedef vector< vpii > vvpii;
typedef vector< pll > vpll;
typedef long double ld;
typedef vector< ld > vld;
 
const ll MOD2 = 1e9 + 7;
const int MOD = 1e9 + 7;
 
const ull infull = numeric_limits<unsigned long long>::max();
 
void fix(int &x, ll MOD) {
    x = (x % MOD);
    if(x < 0) x += MOD;
    return;
}
 
ll lgput(ll a, ll b, ll MOD) {
    ll ret = 1;
    a %= MOD;
    while(b) {
        if(b&1) ret = ret*a % MOD;
        a = a*a % MOD;
        b >>= 1;
    }
 
    return ret;
}
 
ll inv(ll a, ll MOD) {
    return lgput(a, MOD-2, MOD);
}
 
struct f {
    int a, b;
    f(int _a = 0, int _b = 0) : a(_a) ,b(_b) {}
    ll eval(int x) {
        return 1ll*x*a + b;
    }
};
 
int binarySearch(int x, vi &v) {
    int pos = 0;
    int l = 1, r = sz(v);
    while(l <= r) {
        int m = l + r >> 1;
        if(v[m] <= x) {
            pos = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
 
    return pos;
}

const int MAXN = 1e5 + 10;

struct p{
    int x, y;
};

p v[MAXN];
p v2[MAXN];

bool cmpx(p a, p b) {
    return a.x == b.x ? a.x < b.x : a.x < b.x;
}

bool cmpy(p a, p b) {
    return a.y < b.y;
}

ll get(p a, p b) {
    ll nowDist = 1ll*(a.x - b.x)*(a.x - b.x) + 1ll*(a.y - b.y)*(a.y - b.y);
    return nowDist;
}

ll divide(int st, int dr) {
    if(dr <= st + 2) {
        ll ans = 1e18;
        for(int i = st; i <= dr; ++i) {
            for(int j = i + 1; j <= dr; ++j) {
                ans = min(ans, get(v[i], v[j]));
            } 
        }

        sort(v + st, v + dr + 1, cmpy);
        return ans;
    } 

    int mid = st + dr >> 1;
    int midval = v[mid].x;
    ll ans = min(divide(st, mid), divide(mid + 1, dr));
    merge(v + st, v + mid + 1, v + mid + 1, v + dr + 1, v2 + st, cmpy);

    int cnt = 0;
    for(int i = st; i <= dr; ++i) {
        v[i] = v2[i];
        if(1ll*(v[i].x - midval)*(v[i].x - midval) <= ans) v2[++cnt] = v[i];
    }

    for(int i = 1; i <= cnt; ++i) {
        for(int j = i + 1; j <= cnt && 1ll*(v2[i].x - v2[j].x)*(v2[i].x - v2[j].x) <= ans; ++j) {
            ans = min(ans, get(v2[i], v2[j]));
        }
    }

    return ans;
}

int main() { 
    #ifdef BLAT
        freopen("stdin", "r", stdin);
        freopen("stderr", "w", stderr);
    #else
        FO(cmap);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(12);
    srand(time(NULL));

    int n;
    cin >> n;

    for(int i = 1; i <= n; ++i) {
        cin >> v[i].x >> v[i].y;
    }

    sort(v + 1, v + n + 1, cmpx);

    ll ans = divide(1, n);
    cout << setprecision(12) << fixed << sqrt(ans) << '\n';
    return 0;  
}