Cod sursa(job #1428641)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 4 mai 2015 20:47:59
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

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

const int NMax = 100005;
const long long oo = (1LL<<60);
int N;

pair<int,int> P[NMax];


void Read()
{
    fin>>N;
    for(int i=1; i<=N; ++i)
    {
        int x,y;
        fin>>x>>y;
        P[i]= make_pair(x,y);
    }
    sort(P+1,P+N+1);
}

long long Distance(pair<int,int> A, pair<int,int> B)
{
    return 1LL*(B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}

long long DEI(int Left, int Right)
{
    if(Left == Right)
        return oo;

    if(Right-Left == 1)
        return Distance(P[Left],P[Right]);

    int Mid = (Left+Right)/2;

    long long A = DEI(Left,Mid);
    long long B = DEI(Mid+1,Right);
    long long Min = min(A,B);

    vector< pair <int, int> > V;

    for(int i = Left; i<=Right; i++)
        if(abs(P[i].first-P[Mid].first)<=Min)
        V.push_back(P[i]);

    for(int i=0;i< (int) V.size(); ++i)
        for(int j=i+1;j< (int) V.size(); ++j)
            Min = min(Min,Distance(V[i],V[j]));

    return Min;
}

int main()
{
    Read();

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

    return 0;
}