Cod sursa(job #1453061)

Utilizator retrogradLucian Bicsi retrograd Data 22 iunie 2015 18:05:47
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 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);
}

void Read(var &n) {
    fin>>n;
}

int main() {

    var n;
    Read(n);
    for(var i=1; i<=n; i++) {
        Read(X[i]); Read(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];});


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

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

    return 0;
}