Cod sursa(job #1184390)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 12 mai 2014 14:23:32
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 100010;
const long long INF = (1LL << 60);
int N;
pair<int, int> X[NMAX], Aux[NMAX];
long long Dist(pair<int, int> A, pair<int, int> B){
    return 1LL * (A.first - B.first) * (A.first - B.first) + 1LL * (A.second - B.second) * (A.second - B.second);
}
long long Cmap(int Left, int Right){
    if(Left >= Right - 1) return INF;
    if(Right - Left == 2){
        sort(X + Left, X + Right);
        return Dist(X[Left], X[Left + 1]);
    }
    int Mid = (Left + Right) / 2;
    long long CrtD = min(Cmap(Left, Mid), Cmap(Mid, Right));
    merge(X + Left, X + Mid, X + Mid, X + Right, Aux);
    copy(Aux, Aux + Right - Left, X + Left);
    int x = X[Mid].first;
    int K = 0;
    for(int i = Left; i < Right; ++ i)
        if(abs(x - X[i].first) <= CrtD)
            Aux[++ K] = X[i];
    for(int i = 1; i <= K; ++ i)
        for(int j = i + 1; j <= K && j - i <= 8; ++ j)
            CrtD = min(CrtD, Dist(Aux[i], Aux[j]));
    return CrtD;
}

int main(){
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    scanf("%i", &N);
    for(int i = 0; i < N; ++ i) scanf("%d %d", &X[i].first, &X[i].second);
    printf("%.8lf\n", 1.0*sqrt(Cmap(0, N)));
    return 0;
}