Cod sursa(job #1163808)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 1 aprilie 2014 17:12:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

#define INF ~(1LL << 63)
#define Nmax 100005

using namespace std;

pair <int, int> X[Nmax], Y[Nmax], Aux[Nmax];
vector <pair <int, int> > Punct;

int N;
void Citire()
{
    scanf("%d", &N);

    for (int i = 0; i < N; ++i)
        scanf("%d %d", &X[i].first, &X[i].second);
    sort(X, X + N);

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

long long Distanta(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 st, int dr)
{
    if (dr - st <= 1)
        return INF;

    if (dr - st == 2)
    {
        if (Y[st] > Y[st + 1])
            swap(Y[st], Y[st + 1]);
        return Distanta(Y[st], Y[st + 1]);
    }

    int mij = (st + dr) / 2;
    long long Min = min(Cmap(st, mij), Cmap(mij, dr));

    merge(Y + st, Y + mij, Y + mij, Y + dr, Aux);
    copy(Aux, Aux + dr - st, Y + st);
    Punct.clear();

    for (int i = st; i < dr; ++i)
        if (abs(X[mij].first - Y[i].second) <= Min)
            Punct.push_back(Y[i]);

    for (int i = 0; i < Punct.size(); ++i)
        for (int j = i + 1; j < Punct.size() && j - i <= 8; ++j)
            Min = min(Min, Distanta(Punct[i], Punct[j]));

    return Min;
}

void Rezolvare()
{
    long long Dist = Cmap(0, N);
    double Dmin = sqrt(Dist);

    printf("%lf\n", Dmin);
}

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

    Citire();
    Rezolvare();

    return 0;
}