Pagini recente » Cod sursa (job #1286891) | Cod sursa (job #3140259) | Cod sursa (job #1791947) | Cod sursa (job #2099084) | Cod sursa (job #1120218)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cstdlib>
#include <ctime>
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 v[Nmax], tmp[Nmax];
int N;
double distance( Point A, Point B )
{
return sqrt( pow( A.x - B.x, 2.0 ) + pow( A.y - B.y, 2.0 ) );
}
double DI( int st, int dr )
{
int m = st + ( rand() % ( dr - st + 1 ) );
if ( st >= dr ) return inf;
if ( st + 1 == dr )
{
return distance( v[st], v[dr] );
}
double midPoint = v[m].x;
double d1 = DI( st, m );
double d2 = DI( m + 1, dr );
double d = min( d1, d2 );
int i = st, j = m + 1, k = st - 1;
int nr = 0;
for ( int i = st; i <= dr; ++i )
{
if ( abs( v[i].x - midPoint ) <= d )
tmp[ ++nr ] = v[i];
}
double min_dist = d;
for ( int i = 1; i <= nr; ++i )
for ( int j = i - 1; j >= i - 6 && j; --j )
min_dist = min( min_dist, distance( tmp[i], tmp[j] ) );
return min_dist;
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
srand( time( NULL ) );
f >> N;
for ( int i = 1; i <= N; ++i )
{
f >> v[i];
}
sort( v + 1, v + N + 1 );
g << fixed << setprecision( 10 );
g << DI( 1, N ) << endl;
return 0;
}