Cod sursa(job #428614)

Utilizator adrianraduleaRadulea Adrian adrianradulea Data 29 martie 2010 13:48:37
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include<stdio.h>
#include<algo.h>
#include<math.h>
long n,m,i,j,inf,xx[100100],yy[100100],x[100100],y[100100],vectorx[100100],vectory[100100],ind[100100],k,vectorxx[100100],vectoryy[100100];
float sol1,sol2,dmin;
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;
}
float dist(long x1,long y1,long x2,long y2)
{ return sqrt((y1-y2)*(y1-y2)+(x1-x2)*(x1-x2)); }
float cmap(long st,long dr)
{ float dmin=inf;
  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;
  sol1=cmap(st,mij);
  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]; }
  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); inf=2000000000;
  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]]; }
  fprintf(g,"%lf",cmap(1,n));
  fclose(g);
  return 0;
}