Cod sursa(job #606398)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 4 august 2011 09:49:54
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include<fstream.h>
#include<math.h>
#define N 100001
#define M 1000000
typedef struct po
{double x,y;};
po a[N],b[N];
long i,n;
double mi(double p,double q)
{if(p<q)
        return p;
return q;}

void so(po a[N],long l,long r)
{long m=(l+r)/2,i,j,k;
if(l==r)
        return;
so(a,l,m),so(a,m+1,r);
for(i=l,j=m+1,k=l;i<=m||j<=r;)
if(j>r||(i<=m&&(a[i].x<a[j].x||(a[i].x==a[j].x&&a[i].y<a[j].y))))
        b[k++]=a[i++];
else
        b[k++]=a[j++];
for(i=l;i<=r;i++)
        a[i]=b[i];}

double di(po p,po q)
{return M*sqrt(((p.x-q.x)/M)*((p.x-q.x)/M)+((p.y-q.y)/M)*((p.y-q.y)/M));}

double co(long p,long m,long q,double r)
{long i,j,l,t;
for(i=m;i<=q&&a[i].x-a[m].x<r&&i<=m+7;i++);
for(j=m;j>=p&&a[m].x-a[j].x<r&&j>=m-7;j--);
for(l=j+1;l<i;l++)
for(t=l+1;t<=i;t++)
       r=mi(r,di(a[l],a[t]));
return r;}

double cl(po a[N],long p,long q)
{long m=(p+q)>>1,i,j;
double d,t;
if(q-p<4)
       {t=di(a[p],a[p+1]);
       for(i=p;i<q;i++)
       for(j=i+1;j<=q;j++)
       if(t>(d=di(a[i],a[j])))
             t=d;
       return t;}
return co(p,m,q,mi(cl(a,p,m),cl(a,m+1,q)));}

int main()
{ifstream f("cmap.in");
freopen("cmap.out","w",stdout);
f>>n;
for(i=1;i<=n;i++)
       f>>a[i].x>>a[i].y;
so(a,1,n);
printf("%.6lf\n",cl(a,1,n));
return 0;}