Cod sursa(job #588102)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 6 mai 2011 22:15:05
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 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 a,double b)
{if(a<b)
        return a;
return b;}

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

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;
double d;
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++)
       if(r<(d=dist(a[l],a[t])))
                r=d;
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++)
                if((d=dist(a[i],a[j]))<ird)
                        ird=d;
       return ird;}
return combina(p,m,q,min(close(a,p,m),close(a,m+1,q)));}

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