Cod sursa(job #588467)

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

void sort(point a[N],long l,long r)
{long m=(l+r)/2,i,j,k,t;
if(l==r)
        return;
sort(a,l,m);
sort(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(t=l;t<=r;t++)
        a[t]=b[t];}

double dist(point p,point 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 combina(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=min(r,dist(a[l],a[t]));
return r;}

double close(point a[N],long p,long q)
{long m=(p+q)>>1,i,j;
double d,ird;
if(q-p<=3)
       {ird=dist(a[p],a[p+1]);
       for(i=p;i<q;i++)
       for(j=i+1;j<=q;j++)
             {d=dist(a[i],a[j]);
             if(d<ird)
                     ird=d;}
       return ird;}
return combina(p,m,q,min(close(a,p,m),close(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;
sort(a,1,n);
printf("%.6lf\n",close(a,1,n));
f.close();
fclose(stdout);
return 0;}