Cod sursa(job #2345594)

Utilizator _Tudor_Tudor C _Tudor_ Data 16 februarie 2019 15:09:45
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("rmq.in");
ofstream fout("rmq.out");
const long long oo = 1e9;
const long long NMax = 100000;
long long N, k;
pair<long long, long long> P[NMax + 5], X[NMax + 5];

void Read()
{
    fin >> N;
    for(long long i = 0; i < N; i++)
        fin >> P[i].first >> P[i].second;
    sort(P + 1, P + N + 1);
}

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 Left, long long Right)
{
    if(Right == Left)
        return oo;
    if(Right == Left + 1)
        return Dist(P[Left], P[Right]);

    long long Mid = (Left + Right) / 2;
    long long A = DEI(Left, Mid);
    long long B = DEI(Mid + 1, Right);
    long long Min = min(A, B);
    k = 0;
    for(long long i = Left; i <= Right; i++)
        if(abs(P[i].first - P[Mid].first) <= Min)
            X[++k] = P[i];
    for(long long i = 1; i <= k; i++)
        for(long long j = i + 1; j <= k; j++)
            if(Dist(X[i], X[j]) < Min)
                Min = Dist(X[i], X[j]);
    return Min;
}


int main()
{
    Read();
    fout << fixed << setprecision(6) << sqrt(DEI(1, N));
}