Pagini recente » Cod sursa (job #122558) | Cod sursa (job #6868) | Cod sursa (job #561441) | Cod sursa (job #717151) | Cod sursa (job #1014235)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct point {
int x, y;
};
#define MAX_N 100000
#define INF 1000000000
#define EPS 0.0000001
point v[MAX_N], aux[MAX_N];
inline long long square( int x ) {
return ( long long ) x * x;
}
inline double edist( point a, point b ) {
return sqrt( square( a.x - b.x ) + square( a.y - b.y ) );
}
inline bool cmp( point a, point b ) {
if ( a.x < b.x )
return true;
if ( a.x > b.x )
return false;
return ( a.y <= b.y );
}
void read( FILE *fin, int &n ) {
fscanf( fin, "%d", &n );
for ( int i = 0; i < n; ++i )
fscanf( fin, "%d%d", &v[i].x, &v[i].y );
}
void merge( int left, int middle, int right ) {
int i = left, j = middle + 1, pos = left - 1;
while ( i <= middle && j <= right )
if ( v[i].y <= v[j].y ) {
aux[++pos] = v[i];
++i;
} else {
aux[++pos] = v[j];
++j;
}
while ( i <= middle ) {
aux[++pos] = v[i];
++i;
}
while ( j <= right ) {
aux[++pos] = v[j];
++j;
}
for ( i = left; i <= right; ++i )
v[i] = aux[i];
}
double min_dist( int left, int right ) {
// Daca intervalul nu are cel putin 2 elemente, returnez INF.
if ( left >= right )
return INF;
// Daca am doua elemente, returnez distanta dintre ele.
if ( left + 1 == right )
return edist( v[left], v[right] );
// Impart intervalul in doua, dupa dreapta verticala, avand coordonata punctului din mijloc.
int middle = ( left + right ) >> 1, x_mid = v[middle].x;
// Aflu distanta minima dintre doua puncte din stanga si din dreapta dreptei.
double dist_left = min_dist( left, middle ), dist_right = min_dist( middle + 1, right );
double dist = min( dist_left, dist_right );
// Interclasez cele doua intervale de puncte, dupa a doua coordonata.
merge( left, middle, right );
// Caut punctele la distanta mai mica decat cea aflata de punctul din mijloc.
int count = 0;
for ( int i = left; i <= right; ++i )
if ( abs( v[i].x - x_mid ) <= dist )
aux[++count] = v[i];
// Calculez distanta minima intre punctele determinate.
double res = dist;
for ( int i = 1; i <= count; ++i )
for ( int j = i - 6; j >= 0 && j < i; ++j )
res = min( res, edist( aux[i], aux[j] ) );
return res;
}
int main() {
FILE *fin, *fout;
fin = fopen ( "cmap.in", "r" );
int n;
read( fin, n );
fclose( fin );
sort( v, v + n, cmp );
fout = fopen( "cmap.out", "w" );
fprintf( fout, "%lf\n", min_dist( 0, n - 1 ) );
fclose( fout );
}