Cod sursa(job #472662)

Utilizator ionutz32Ilie Ionut ionutz32 Data 26 iulie 2010 01:11:13
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

#define inf (double)(0x7fffffff*sqrt(2))

struct punct
{
    int x,y;
} v[100005],y[100005];
int n,i;
struct cmp
{
    inline bool operator()(const punct &a,const punct &b)const
    {
        return a.x<b.x;
    }
};
struct cmpy
{
    inline bool operator()(const punct &a,const punct &b)const
    {
        return a.y<b.y;
    }
};

inline double dist(punct a,punct b)
{
    return sqrt(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}

inline int minim(int a,int b)
{
    if (a<b)
        return a;
    return b;
}

double sol(int st,int dr)
{
    int i,j,mid,a,b,c,x,nr1,nr2;
    double aux,ret,s1,s2;
    if (st>dr)
        return inf;
    if (dr-st+1<=3)
    {
        ret=inf;
        for (i=st;i<dr;++i)
            for (j=i+1;j<=dr;++j)
            {
                aux=dist(v[i],v[j]);
                if (aux<ret)
                    ret=aux;
            }
        return ret;
    }
    mid=st+((dr-st)>>1);
    x=v[mid].x;
    s1=sol(st,mid);
    s2=sol(mid+1,dr);
    if (s2<s1)
        s1=s2;
    a=st;
    b=mid;
    while (a<=b)
    {
        c=a+((b-a)>>1);
        if (x-v[c].x>=s1)
            a=c+1;
        else
            b=c-1;
    }
    nr1=b+1;
    a=mid+1;
    b=dr;
    while (a<=b)
    {
        c=a+((b-a)>>1);
        if (v[c].x-x>=s1)
            b=c-1;
        else
            a=c+1;
    }
    nr2=b;
    for (i=nr1;i<=nr2;++i)
        y[i-nr1+1]=v[i];
    sort(y+1,y+nr2-nr1+2,cmpy());
    ret=inf;
    for (i=1;i<=nr2-nr1+1;++i)
        for (j=i+1;j<=minim(i+7,nr2-nr1+1);++j)
        {
            aux=dist(y[i],y[j]);
            if (aux<ret)
                ret=aux;
        }
    if (s1<ret)
        return s1;
    return ret;
}

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;++i)
        scanf("%d %d",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp());
    printf("%.6lf",sol(1,n));
    return 0;
}