Cod sursa(job #2357195)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 27 februarie 2019 10:41:13
Problema Cele mai apropiate puncte din plan Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int NMax = 100000;

const long long oo = 4e18;

int N, K;

pair <long long, long long> P[NMax + 5], V[NMax + 5];

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 DEI(long long L, long long R)
{
    if(L == R)
        return oo;

    if(L == R - 1)
        return Dist(P[L], P[R]);

    long long M = (L + R) >> 1, A, B;

    A = DEI(L, M), B = DEI(M + 1, R);

    long long Sol = min(A, B); K = 0;

    for(int i = L; i <= R; i++)
        if(abs(P[i].first - P[M].first) <= Sol)
            V[++K] = P[i];

    sort(V + 1, V + K + 1);

    for(int i = 1; i <= K; i++)
    {
        for(int j = i + 1; j <= i + 8 && j <= K; j++)
            Sol = min(Sol, Dist(P[i], P[j]));
    }
    return Sol;
}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> P[i].first >> P[i].second;

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

    fout << fixed << setprecision(6) << sqrt(DEI(1, N)) << '\n';

    fin.close();
    fout.close();

    return 0;
}