Cod sursa(job #1589254)

Utilizator touristGennady Korotkevich tourist Data 3 februarie 2016 21:15:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define Nmax 100005
#define INF (1LL<<62)

using namespace std;

pii Ox[Nmax],Oy[Nmax],Aux[Nmax];
int n;
long long ans=INF;

inline long long Dist(pii A, pii B)
{
    return 1LL*(A.fi-B.fi)*(A.fi-B.fi) + 1LL*(A.se-B.se)*(A.se-B.se);
}

inline void Solve(int st, int dr)
{
    if(st==dr)
    {
        Oy[st]=Ox[st]; return;
    }
    int mij=((st+dr)>>1);
    Solve(st,mij); Solve(mij+1,dr);
    merge(Oy+st,Oy+mij+1,Oy+mij+1,Oy+dr+1,Aux+1);
    copy(Aux+1,Aux+(dr-st+2),Oy+st);
    for(int i=st;i<=dr;++i)
        for(int j=i+1;j<=i+7 && j<=dr;++j) ans=min(ans,Dist(Oy[i],Oy[j]));
}

int main()
{
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");
    cin>>n;
    for(int i=1;i<=n;++i) cin>>Ox[i].fi>>Ox[i].se;
    sort(Ox+1,Ox+n+1);
    Solve(1,n);
    cout<<setprecision(10)<<fixed<<sqrt(1.0*ans)<<"\n";
    return 0;
}