Pagini recente » Cod sursa (job #2341943) | Cod sursa (job #1546726)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#define MAX_N 100000
#define INF 800000000000000000LL
#define MAX_PICK 6
#define MIN(A, B) ((A) < (B) ? (A) : (B))
#define MAX(A, B) ((A) > (B) ? (A) : (B))
typedef struct {
int x, y;
} point;
point v[MAX_N];
point tmpMerge[MAX_N];
void myqsort( int begin, int end ) {
int b = begin, e = end;
int pivot = v[rand() % (end - begin + 1) + begin].x;
point aux;
while ( b <= e ) {
while ( v[b].x < pivot ) b++;
while ( v[e].x > pivot ) e--;
if ( b <= e ) {
aux = v[b]; v[b] = v[e]; v[e] = aux;
b++; e--;
}
}
if ( begin < e ) myqsort( begin, e );
if ( b < end ) myqsort( b, end );
}
long long pointDistance( point *A, point *B ) {
return 1LL * ( A->x - B->x ) * ( A->x - B->x ) + 1LL * ( A->y - B->y ) * ( A->y - B->y );
}
long long cmap( int begin, int end ) {
point aux;
int i, j, k, med, medX;
long long distB, distE, dist;
if ( end - begin == 1 ) {
if ( v[begin].y > v[end].y ) {
aux = v[begin]; v[begin] = v[end]; v[end] = aux;
}
return pointDistance( &v[begin], &v[end] );
} else if ( end - begin > 1 ) {
med = ( begin + end ) / 2;
medX = v[med].x;
distB = cmap( begin, med ); distE = cmap( med + 1, end );
dist = MIN( distB, distE );
i = begin; j = med + 1; k = begin;
while ( i <= med && j <= end ) {
if ( v[i].y < v[j].y ) {
tmpMerge[k] = v[i];
i++;
} else {
tmpMerge[k] = v[j];
j++;
}
k++;
}
while ( i <= med ) tmpMerge[k++] = v[i++];
while ( j <= end ) tmpMerge[k++] = v[j++];
for ( i = begin; i <= end; i++ )
v[i] = tmpMerge[i];
k = 0;
for ( i = begin; i <= end; i++ ) {
if ( abs( v[i].x - medX ) <= dist ) {
tmpMerge[k++] = v[i];
}
}
for ( i = 1; i < k; i++ ) {
med = MAX( 0, i - MAX_PICK );
for ( j = i - 1; j >= med; j-- ) {
distB = pointDistance( &tmpMerge[i], &tmpMerge[j] );
if ( distB < dist ) {
dist = distB;
}
}
}
return dist;
}
return INF;
}
int main( void ) {
FILE *fin, *fout;
int n, i;
fin = fopen( "cmap.in", "r" );
fscanf( fin, "%d", &n );
for ( i = 0; i < n; i++ ) {
fscanf( fin, "%d%d", &v[i].x, &v[i].y );
}
fclose( fin );
myqsort( 0, n - 1 );
fout = fopen( "cmap.out", "w" );
fprintf( fout, "%.6f\n", sqrt( cmap( 0, n - 1 ) ) );
fclose( fout );
return 0;
}