Cod sursa(job #1453063)

Utilizator retrogradLucian Bicsi retrograd Data 22 iunie 2015 18:08:30
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<bits/stdc++.h>

using namespace std;
typedef int var;

#define MAXN 100005
var X[MAXN], Y[MAXN], XI[MAXN], YI[MAXN];

ifstream fin("cmap.in");
ofstream fout("cmap.out");


double dist(var i, var j) {
    var dx = X[i] - X[j];
    var dy = Y[i] - Y[j];
    return sqrt(1LL * dx * dx + 1LL * dy * dy);
}

int main() {

    var n;
    fin>>n;
    for(var i=1; i<=n; i++) {
        fin>>X[i]>>Y[i];
        XI[i] = i; YI[i] = i;
    }

    sort(XI+1, XI+n+1, [](var a, var b) {return X[a] < X[b];});
    sort(YI+1, YI+n+1, [](var a, var b) {return Y[a] < Y[b];});
    XI[n+1] = YI[n+1] = n+1;
    X[n+1] = Y[n+1] = 2e9;

    double mind = 1e15;
    for(var i=1; i<=n; i++) {
        for(var j=i+1; X[XI[j]] - X[XI[i]] <= mind; j++)
            mind = min(mind, dist(XI[i], XI[j]));

        for(var j=i+1; Y[YI[j]] - Y[YI[i]] <= mind; j++)
            mind = min(mind, dist(YI[i], YI[j]));
    }
    fout<<fixed<<setprecision(10)<<mind;

    return 0;
}