Cod sursa(job #528167)

Utilizator DraStiKDragos Oprica DraStiK Data 2 februarie 2011 12:02:47
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <algorithm>
#include <cmath>
using namespace std;

#define INF (1ll<<60)
#define DIM 100005
#define sc second
#define fs first
#define LIM 8

pair <int,int> v[DIM];
int ind[DIM];
int n,m;

void read ()
{
    int i;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
        scanf ("%d%d",&v[i].fs,&v[i].sc);
}

inline long long dist (pair <int,int> a,pair <int,int> b)
{
    return 1LL*(a.fs-b.fs)*(a.fs-b.fs)+1LL*(a.sc-b.sc)*(a.sc-b.sc);
}

struct cmp
{
    bool operator () (const int &a,const int &b)
    {
        return v[a].sc<v[b].sc;
    }
};

long long calc (int st,int dr)
{
    long long dst;
    int mij,i,j;

    if (dr-st<=2)
    {
        dst=INF;
        for (i=st; i<dr; ++i)
            for (j=i+1; j<=dr; ++j)
                dst=min (dst,dist (v[i],v[j]));

        return dst;
    }

    mij=(st+dr)/2; dst=min (calc (st,mij),calc (mij+1,dr));
    m=0;
    for (i=st; i<=dr; ++i)
        if (abs (v[i].sc-v[mij].sc)<=dst)
            ind[++m]=i;
    sort (ind+1,ind+m+1,cmp ());
    for (i=1; i<m; ++i)
        for (j=i+1; j<=m && j-i<LIM; ++j)
            dst=min (dst,dist (v[ind[i]],v[ind[j]]));

    return dst;
}

int main ()
{
    freopen ("cmap.in","r",stdin);
    freopen ("cmap.out","w",stdout);

    read ();
    printf ("%.6lf",sqrt (calc (1,n)));

    return 0;
}