Cod sursa(job #410957)

Utilizator petrecgClinciu Glisca Petre petrecg Data 4 martie 2010 17:38:22
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <stdio.h>
#include <math.h>
double sol;
long n,i,x[100100],y[100100],v[100100],a[100100],b[100100];
double dist(long i,long j)
{double dx,dy;
 dx=x[i]-x[j];
 dy=y[i]-y[j];
 return sqrt((dx)*(dx)+(dy)*(dy));
}

int cmp(long i,long j)
{if(x[i]<x[j]||(x[i]==x[j]&&y[i]<y[j]))return 1;
 return 0;
}

void merge_sort(long st,long dr)
{long mij=st+((dr-st)>>1),i,j,k;
 if(st!=dr)
  {merge_sort(st,mij);
   merge_sort(mij+1,dr);
   for(i=st,j=mij+1,k=st;i<=mij||j<=dr;)
    if(j>dr||(i<=mij&&cmp(i,j)))
     {a[k++]=x[i++];b[k-1]=y[i-1];}
    else
     {a[k++]=x[j++];b[k-1]=y[j-1];}
   for(k=st;k<=dr;k++){x[k]=a[k];y[k]=b[k];}
  }
}

double cmap(long st,long dr)
{double dmin=2000000000,dd;
 long i,j;
 if(dr-st<3)
 {for(i=st;i<dr;i++)
   for(j=i+1;j<=dr;j++)
    {dd=dist(i,j);
     if(dd<dmin)dmin=dd;
     if(y[i]>y[j])
      {x[0]=x[i];x[i]=x[j];x[j]=x[0];y[0]=y[i];y[i]=y[j];y[j]=y[0];}
    }
  return dmin;
 }
 long mij,xx,k=st,xxx;
 double s1,s2;
 mij=st+((dr-st)>>1);
 xx=x[mij];
 s1=cmap(st,mij);
 s2=cmap(mij+1,dr);
 if(s2<s1)s1=s2;
 for(i=st,j=mij+1;i<=mij||j<=dr;)
  if((j>dr)||(i<=mij&&y[i]<=y[j])){a[k++]=x[i++];b[k-1]=y[i-1];}
			   else {a[k++]=x[j++];b[k-1]=y[j-1];}
 k=0;
 for(i=st;i<=dr;i++)
  {x[i]=a[i];y[i]=b[i];
   xxx=x[i]-xx;
   if(xxx<0)xxx=-xxx;
   if(xxx<=s1){k++;v[k]=i;}
  }
 for(i=1;i<k;i++)
  for(j=i+1;j<=k&&j<=i+7;j++)
   {dd=dist(v[i],v[j]);
    if(dd<dmin)dmin=dd;
   }
 if(dmin>s1)dmin=s1;
 return dmin;
}

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