Cod sursa(job #546142)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 4 martie 2011 15:02:02
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<stdio.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)>>1,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=m,j=m-1,k=0,z[N],l,t,w[N],o=0;
double d;
while(a[i].x-a[m].x<r&&i<=q)
      z[++k]=i++;
while(a[m].x-a[j].x<r&&j>=p)
      w[++o]=j--;
for(l=1;l<=k;l++)
      {for(t=1;t<=o;t++)
      if((d=dist(a[z[l]],a[w[t]]))<r)
             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++)
                   {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()
{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;}