Cod sursa(job #1761008)

Utilizator PaulStighiStiegelbauer Paul-Alexandru PaulStighi Data 21 septembrie 2016 18:00:16
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>

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

const int NMax = 100000;
const long long oo = 1LL << 60;
pair <int, int> P[NMax + 5];
pair <int, int> Q[NMax + 5];
int N;

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

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 DEI(int Left, int Right)
{
    if(Left==Right)
        {
            return oo;
        }
    if(Right - Left == 1)
        {
            return Dist(P[Left],P[Right]);
        }
    int Mid = (Left + Right) / 2;
    long long Min1 = DEI(Left, Mid);
    long long Min2 = DEI(Mid + 1, Right);
    long long Min = min(Min1,Min2);
    int k = 0;
    for(int i = Left; i <= Right; ++i)
        {
            if(Dist(P[i],P[Mid]) < Min)
                Q[++k] = P[i];
        }
    for(int i = 1; i <= k; i++)
        for(int j = i+1; j <= k; j++)
            Min = min(Min, Dist(P[i],P[j]));

    return Min;
}

void Print()
{
    fout << fixed << setprecision(6) << sqrt(DEI(1,N));
}

int main()
{
    Read();
    Print();
    return 0;
}