Cod sursa(job #2827274)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 5 ianuarie 2022 15:56:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <bits/stdc++.h>
 
using namespace std;
 
inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}
 
typedef long long i64;
typedef pair <i64, i64> pii;
 
const i64 INF = 4e18;
 
vector <pii> V(100005), X, Y;
 
i64 dist(const pii &a, const pii &b) {
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
 
i64 go(int st, int dr, vector <pii> &X, vector <pii> &Y) {
    if(st >= dr - 1)
        return INF;
    else if(dr - st == 2) {
        if(Y[st] > Y[st + 1]) {
            swap(Y[st], Y[st + 1]);
        }
        return dist(X[st], X[st + 1]);
    }
 
    int mid = (st + dr) / 2;
    i64 best = min(go(st, mid, X, Y), go(mid, dr, X, Y));
 
    sort(Y.begin() + st, Y.begin() + dr);
 
    int v_size = 0;
    for(int i = st;i < dr;i++)
        if(abs(Y[i].second - X[mid].first) <= best)  {
            V[v_size++] = Y[i];
        }
 
    for(int i = 0;i < v_size - 1;i++) {
        for(int j = i + 1;j < v_size && j - i < 8;j++)
            best = min(best, dist(V[i], V[j]));
    }
 
    return best;
}
 
void solve() {
    int N; cin >> N;

    X.resize(N), Y.resize(N);
    for(int i = 0;i < N;i++)  {
        cin >> X[i].first >> X[i].second;
    }
 
    sort(X.begin(), X.end());
    for(int i = 0;i < (int)X.size();i++)
        Y[i] = make_pair(X[i].second, X[i].first);
 
    cout << fixed << setprecision(6) << sqrt(go(0, (int)X.size(), X, Y));
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    Open("cmap");
 
    int T = 1;
    for(;T;T--) {
        solve();
    }
 
    return 0;
}