Cod sursa(job #983858)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 12 august 2013 20:44:49
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define i64 long long
#define NMax 100005
#define oo 1LL<<60
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pair <i64, i64> X[NMax],Array[NMax];
int N;
void Read()
{
    fin>>N;
    for(int i=1;i<=N;i++)
        {
            int x,y;
            fin>>x>>y;
            X[i]=make_pair(x,y);
        }
    sort(X+1,X+N+1);
}
inline i64 Dist(pair <i64,i64> A, pair <i64,i64>B)
{
 return (B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}
i64 DEI(int Left, int Right)
{
    if(Left==Right)
        return oo;
    if(Right-Left==1)
        {
            return Dist(X[Left],X[Right]);
        }
    int Mid=(Left+Right)/2;
    i64 a=DEI(Left,Mid);
    i64 b=DEI(Mid+1,Right);
    long long V=min(a,b);
    int k=0;
    for(int i=Left;i<=Right;i++)
        {
            if(X[i].first-X[Mid].first<=V)
                {
                    Array[++k]=X[i];
                }
        }
    for(int i=1;i<=k;i++)
        for(int j=i+1;j<=k;j++)
            V=min(V,Dist(Array[i],Array[j]));
    return V;
}

void Print()
{
    fout<<fixed<<setprecision(6)<<sqrt((double)DEI(1,N))<<'\n';
}
int main()
{
    Read();
    Print();
    return 0;
}