Pagini recente » Cod sursa (job #3121649) | Cod sursa (job #1961876) | Cod sursa (job #1342002) | Cod sursa (job #2897866) | Cod sursa (job #1120376)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
const int Nmax = 100002;
const double inf = 1e18;
struct Point
{
double x, y;
Point( const double _x = 0, const double _y = 0 )
{
x = _x;
y = _y;
}
bool operator < ( const Point P ) const
{
if ( x != P.x )
return x < P.x;
else
return y < P.y;
}
friend istream& operator >> ( istream &f, Point &P )
{
f >> P.x >> P.y;
return f;
}
};
Point X[Nmax], Y[Nmax], aux[Nmax];
int N;
double DIST( Point A, Point B )
{
return ( pow( A.x - B.x, 2.0 ) + pow( A.y - B.y, 2.0 ) );
}
double DI( int st, int dr )
{
if ( st >= dr - 1 ) return inf;
if ( st + 2 == dr )
{
sort( Y + st, Y + dr );
return DIST( X[st], X[st + 1] );
}
double d;
int m = ( st + dr ) / 2;
d = min( DI( st, m ), DI( m, dr ) );
merge( Y + st, Y + m, Y + m, Y + dr, aux );
copy( aux, aux + dr - st, Y + st );
int nr = 0;
for ( int i = st; i < dr; ++i )
if ( abs( Y[i].y - X[m].x ) <= d )
aux[ ++nr ] = Y[i];
double min_dist = inf;
for ( int i = 1; i <= nr; ++i )
for ( int j = i + 1; j <= nr && j - i < 8; ++j )
min_dist = min( min_dist, DIST( aux[i], aux[j] ) );
return min_dist;
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
f >> N;
for ( int i = 0; i < N; ++i )
{
f >> X[i];
Y[i] = Point( X[i].y, X[i].x );
}
g << fixed << setprecision( 10 );
g << sqrt( DI( 0, N ) ) << endl;
return 0;
}