Pagini recente » Cod sursa (job #159078) | Cod sursa (job #2987791) | Cod sursa (job #2923944) | Cod sursa (job #1641331) | Cod sursa (job #1983957)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<limits.h>
#include<float.h>
#define Nmax 100010
typedef struct { int x, y;}punct;
punct v[Nmax],w[Nmax];
int n;
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
double dist ( punct a, punct b)
{
double difx=a.x-b.x;
double dify=a.y-b.y;
return sqrt ( difx*difx + dify*dify ) ;
}
double divide ( int st, int dr)
{
if ( dr-st < 3 )
{
double D, Dmin=DBL_MAX;
int i, j;
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
{
D=dist(v[i],v[j]);
if(D<Dmin)
Dmin=D;
}
return Dmin;
}
int m=(st+dr)/2;
int d=v[m].x;
double S1 = divide ( st, m ) ;
double S2 = divide ( m+1, dr ) ;
double S = S1;
if(S2<S1) S=S2;
int i,j=m+1,k=0;
for(i=st;i<=m;i++)
if( abs(v[i].x-d) <= S ) break;
while( i <= m && j <= dr && abs(v[j].x-d) <= S )
if( v[i].y < v[j].x ) w[++k]=v[i++];
else w[++k]=v[j++];
while ( i <= m ) w[++k]=v[i++];
while ( j <= dr && abs(v[j].x-d) <= S ) w[++k]=v[j++];
double D, Dmin=DBL_MAX;
for(i=1;i<k;i++)
for(j=i+1; j<=(i+7) && j<=k; j++)
{
D=dist(w[i],w[j]);
if(D<Dmin) Dmin=D;
}
if(Dmin>S) Dmin=S;
return Dmin;
}
int main()
{FILE *f,*g;
int n;
double min;
f=fopen("cmap.in","r");
g=fopen("cmap.out","w");
fscanf(f,"%d",&n);
int i;
for(i=1;i<=n;i++)
fscanf(f,"%d%d",&v[i].x,&v[i].y);
qsort(v+1,n,8,cmpfunc);
min=divide(0,n-1);
fprintf(g,"%lf\n",min);
// printf("%lf\n(%d %d) (%d %d)",dist(v[ci],v[cj]),v[ci].x,v[ci].y,v[cj].x,v[cj].y);
return 0;
}