Cod sursa(job #411445)

Utilizator probaproba proba proba Data 4 martie 2010 21:45:20
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 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,i1,j1;
 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;
    }
  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;
 k=0;
 for(i=mij;i>=st&&xx-x[i]<=s1;i--);i++;
 for(j=mij+1;j<=dr&&x[j]-xx<=s1;j++);j--;
 for(i1=i;i1<j;i1++)
  for(j1=i1+1;j1<=j;j1++)
   {dd=dist(i1,j1);
    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;
}