Cod sursa(job #2046416)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 23 octombrie 2017 19:51:50
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
#define NMAX 100005
//#define min(a, b) ( ( a < b ) ? a : b )
 
using namespace std;
ifstream f ("cmap.in");
ofstream g ("cmap.out");
 
typedef long long ll;
typedef vector < pair < ll, ll > > vect;
vect X, V(NMAX);
const ll INF = 4e18;
int n;
 
ll dist(const pair < ll, ll > & x, const pair < ll, ll > & y) {
    return (x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second);
}
 
ll ans(int st, int dr)
{
    if (st >= dr - 1) return INF;
    if (dr - st == 2) return dist(X[st], X[st + 1]);
    int mid = (st + dr) / 2;
    ll best = min(ans(st, mid), ans(mid, dr));
    int m = 0;
    for (int i = st; i < dr; i++)
        if (abs(X[i].second - X[mid].first) <= best)
            V[m++] = X[i];
    for (int i = 0; i < m; i++)
        for (int j = i + 1; j < m && j - i < 8; j++)
            best = min(best, dist(V[i], V[j]));
    return best;
}
 
int main()
{
    f>>n;
    X.resize(n);
    for (int i = 0; i < n; i++)
        f>>X[i].first>>X[i].second;
    sort(X.begin(), X.end());
    g<<fixed<< setprecision(6)<<sqrt(ans(0, n));
    return 0;
}