Cod sursa(job #1495236)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 2 octombrie 2015 19:23:50
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

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

const long long oo = 100000000000000LL;
const int NMax = 100005;

pair <long long, long long> P[NMax],Q[NMax];

int N;

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(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 A = DEI (Left, Mid);
    long long B = DEI (Mid+1, Right);

    long long Min = min(A,B);

    int k = 0;

    for(int i = Left; i<=Right; i++)
        if(abs(P[i].first-P[Mid].first)<=Min)
            Q[++k] = make_pair(P[i].second, P[i].first);

    sort(Q+1,Q+k+1);

    for(int i = 1; i<=k ; i++)
        for(int j = i+1; j<=k && (j<=i+8)  ; j++)
            Min = min(Min,Dist(Q[i],Q[j]));

    return Min;




}


int main()
{

    fin>>N;

    for(int i=1; i<=N; i++)
            fin>>P[i].first>>P[i].second;

    sort(P+1,P+N+1);

    fout<<fixed<<setprecision(7)<<sqrt(DEI(1,N))<<"\n";

    return 0;
}