Cod sursa(job #1184562)

Utilizator andreiiiiPopa Andrei andreiiii Data 13 mai 2014 10:45:47
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

const int Nmax = 100005;
const long long INF = 1LL << 60;

pair<long long, long long> A[Nmax], B[Nmax], Aux[Nmax];


long long modul(long long k) {return (k<0?(-k):k);}

long long dist(pair<long long, long long> a, pair<long long, long long> b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

long long Solve(const int l, const int r)
{
    if(l >= r) return INF;
    if(l == r - 1)
    {
        if(B[l] > B[r])
            swap(B[l], B[r]);

        return dist(B[l], B[r]);
    }

    int mid = (l + r) / 2;
    long long ret = min(Solve(l, mid), Solve(mid+1, r));

    merge(B + l, B + mid +1, B + mid + 1, B + r + 1, Aux);
    copy(Aux, Aux + (r - l + 1), B + l);

    int N = 0;
    for(int i = l; i <= r; i++)
        if(modul(B[i].second - A[i].first) <= ret) Aux[++N] = B[i];

    for(int i = 1; i <= N; i++)
        for(int j = i + 1; j <= i + 7 && j <= N; j++)
            ret=min(ret, dist(Aux[i], Aux[j]));

    return ret;
}

int main()
{
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);

    int N;
    scanf("%d", &N);

    for(int i = 1; i <= N; i++)
        scanf("%lld%lld", &A[i].first, &A[i].second);

    sort(A + 1, A + N + 1);

    for(int i = 1; i <= N; i++)
        B[i] = make_pair(A[i].first, A[i].second);

    long long Sol = Solve(1, N);

    printf("%.6lf\n", sqrt(Sol));
}