Cod sursa(job #1379414)

Utilizator TheFFOFratila Florin Ovidiu TheFFO Data 6 martie 2015 17:47:04
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

#define NMAX 100005
#define LINF ~(1LL<<63)
#define i64 long long

using namespace std;

int n;
pair<i64,i64> X[NMAX],Y[NMAX],v[NMAX];

void read()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%lld%lld",&X[i].first,&X[i].second);
    sort(X,X+n);
    for(int i=0;i<n;++i)
    {
        Y[i].second=X[i].first;
        Y[i].first=X[i].second;
    }
}

inline i64 dist(const pair<i64,i64> a,const pair<i64,i64> b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}

i64 cmap(int st,int dr)
{
    if(dr-st<=1)
        return LINF;
    if(dr-st==2)
    {
        if(Y[st]>Y[st+1])
            swap(Y[st],Y[st+1]);
        return dist(X[st],X[st+1]);
    }
    int mid=st+(dr-st)/2;
    i64 best=min(cmap(st,mid),cmap(mid,dr));
    int v_size=0;
    for(int i=st;i<dr;++i)
        if(abs(Y[i].second-X[mid].first<=best))
            v[++v_size]=Y[i];
    for(int i=0;i<v_size;++i)
        for(int j=i+1;j<=v_size&&j-i<8;++j)
            best=min(best,dist(v[i],v[j]));
    return best;
}


int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    read();
    i64 d=cmap(0,n);
    double Ans=sqrt((double)d);
    printf("%lf",Ans);
}