Cod sursa(job #1414495)

Utilizator loturiLoturi super ruperi loturi Data 2 aprilie 2015 17:44:44
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 100005

using namespace std;

pair < int, int > Ox[Nmax],Oy[Nmax],Aux[Nmax];
long long sol=(1LL<<62);

inline 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);
}

inline void Solve(int Left, int Right)
{
    if(Left>=Right) return;
    int mid=(Left+Right)/2;
    Solve(Left,mid); Solve(mid+1,Right);
    merge(Oy+Left,Oy+mid+1,Oy+mid+1,Oy+Right+1,Aux+1);
    copy(Aux+1,Aux+Right-Left+2,Oy+Left);
    for(int i=Left;i<=Right;++i)
        for(int j=i+1;j<=i+7;++j) sol=min(sol,Dist(Oy[i],Oy[j]));
}

int main()
{
    int i,n;
    ifstream fin ("cmap.in");
    ofstream fout ("cmap.out");
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>Ox[i].first>>Ox[i].second;
        Oy[i].first=Ox[i].second; Oy[i].second=Ox[i].first;
    }
    sort(Ox+1,Ox+n+1);
    Solve(1,n);
    fout<<setprecision(10)<<fixed<<sqrt(1.0*sol);
    return 0;
}