Cod sursa(job #2345588)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 16 februarie 2019 15:06:07
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int oo = 1e9;
const int NMax = 100000;
int N,k;
pair <int,int> P[NMax + 5], X[NMax + 5];
void Read()
{
    fin >> N;
    for(int i = 1; i <= N; ++i)
        fin >> P[i].first >> P[i].second;
    sort(P+1,P+N+1);
}
int Dist(pair <int,int> A, pair <int,int> B)
{
    return (A.first - B.first)*(A.first - B.first) + (A.second - B.second)*(A.second - B.second);
}
int DEI(int Left, int Right)
{
    if(Right == Left)
        return oo;
    if(Right == Left + 1)
        return (Dist(P[Left],P[Right]));
    int Mid = (Left + Right) / 2;
    int A = DEI(Left, Mid);
    int B = DEI(Mid+1,Right);
    int Min = min(A,B);
    k=0;
    for(int i = Left; i <= Right; ++i)
        if(abs(P[i].first - P[Mid].first) <= Min)
            X[++k] = P[i];
     for(int i = 1; i <= k; ++i)
         for(int 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));
    return 0;
}