Cod sursa(job #1166165)

Utilizator poptibiPop Tiberiu poptibi Data 3 aprilie 2014 12:10:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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], Y[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(Y + Left, Y + Right);
        return Dist(Y[Left], Y[Left + 1]);
    }

    int Mid = (Left + Right) / 2;
    long long CrtD = min(Cmap(Left, Mid), Cmap(Mid, Right));

    merge(Y + Left, Y + Mid, Y + Mid, Y + Right, Aux);
    copy(Aux, Aux + Right - Left, Y + Left);

    int K = 0;
    for(int i = Left; i < Right; ++ i)
        if(abs(X[Mid].first - Y[i].second) <= CrtD)
            Aux[++ K] = Y[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("%i %i", &X[i].first, &X[i].second);

    sort(X, X + N);

    for(int i = 0; i < N; ++ i) Y[i] = make_pair(X[i].second, X[i].first);

    printf("%.6lf\n", sqrt(1.0 * Cmap(0, N)));
}