Cod sursa(job #428717)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 29 martie 2010 14:59:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include<stdio.h>
#include<algo.h>
#include<math.h>
long n,m,i,j,xx[100100],yy[100100],x[100100],y[100100],vectorx[100100],vectory[100100],ind[100100],k,vectorxx[100100],vectoryy[100100];
long long inf; double aux;
FILE *f,*g;
int cmp(long p,long q)
{ if((xx[p]<xx[q])||(xx[p]==xx[q]&&yy[p]<yy[q])) return 1;
  return 0;
}
int cmp1(long p,long q)
{ if((vectory[p]<vectory[q])||(vectory[p]==vectory[q]&&vectorx[p]<vectory[q])) return 1;
  return 0;
}
long double dist(long x1,long y1,long x2,long y2)
{ double dx; double dy;
  dx=x1-x2; dy=y1-y2;
  return sqrt(dx*dx+dy*dy);
}
double cmap(long st,long dr)
{ long double dmin=200000000000000000LL;
  if(dr-st+1<=3) { for(i=st;i<dr;i++) for(j=i+1;j<=dr;j++) if(dist(x[i],y[i],x[j],y[j])<dmin) dmin=dist(x[i],y[i],x[j],y[j]); return dmin; }
  long mij=(st+dr)/2;
  long double sol1=cmap(st,mij);
  long double sol2=cmap(mij+1,dr);
  if(sol2<sol1) sol1=sol2;
  for(i=st;i<=mij;i++) if(x[mij]-x[i]<sol1) break; if(i==mij+1) i=mij;
  for(j=dr;j>=mij+1;j--) if(x[j]-x[mij]<sol1) break; if(j==mij) j=mij+1;
  for(k=i;k<=j;k++) { vectorx[k-i+1]=x[k]; vectory[k-i+1]=y[k]; }
  long k=j-i+1; for(i=1;i<=k;i++) ind[i]=i; sort(ind+1,ind+k+1,cmp1); for(i=1;i<=k;i++) { vectorxx[i]=vectorx[ind[i]]; vectoryy[i]=vectory[ind[i]]; }
  for(i=1;i<k;i++) for(j=i+1;j<=i+7&&j<=k;j++) if(dist(vectorxx[i],vectoryy[i],vectorxx[j],vectoryy[j])<sol1) sol1=dist(vectorxx[i],vectoryy[i],vectorxx[j],vectoryy[j]);
  return sol1;
}    
int main()
{ f=fopen("cmap.in","r"); g=fopen("cmap.out","w");
  fscanf(f,"%ld",&n); 
  for(i=1;i<=n;i++) { fscanf(f,"%ld%ld",&xx[i],&yy[i]); ind[i]=i; } 
  sort(ind+1,ind+n+1,cmp);
  for(i=1;i<=n;i++) { x[i]=xx[ind[i]]; y[i]=yy[ind[i]]; }
  aux=cmap(1,n);
  fprintf(g,"%lf",aux);
  fclose(g);
  return 0;
}