Pagini recente » Cod sursa (job #607938) | Cod sursa (job #1635700) | Cod sursa (job #714480) | Cod sursa (job #1942747) | Cod sursa (job #1120955)
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
const int Nmax = 100005;
const double inf = 1e18;
const double EPS = 1e-18;
struct Point
{
double x, y;
Point( const double a = 0, const double b = 0 )
{
x = a;
y = b;
}
bool operator < ( const Point P ) const
{
return x < P.x;
}
friend istream& operator >> ( istream &f, Point &P )
{
f >> P.x >> P.y;
return f;
}
};
Point v[Nmax], tmp[Nmax];
int N;
double DIST( Point A, Point B )
{
return sqrt( ( A.x - B.x ) * ( A.x - B.x ) + ( A.y - B.y ) * ( A.y - B.y ) );
}
bool cmp( Point A, Point B )
{
return A.y < B.y;
}
double DI( int st, int dr )
{
if ( st >= dr ) return inf;
if ( st + 1 == dr ) return DIST( v[st], v[dr] );
int m = ( st + dr ) / 2;
double d1 = DI( st, m );
double d2 = DI( m + 1, dr );
double d = min( d1, d2 );
int k = 0;
for ( int i = st; i <= dr; ++i )
{
if ( abs( v[m].x - v[i].x ) <= d )
tmp[ k++ ] = v[i];
}
sort( tmp, tmp + k, cmp );
double sol = d;
for ( int i = 0; i < k; ++i )
{
for ( int j = i + 1; j < k && tmp[j].y - tmp[i].y < sol; ++j )
{
double dist = DIST( tmp[i], tmp[j] );
sol = min( sol, dist );
}
}
return d;
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
f >> N;
for ( int i = 0; i < N; ++i )
f >> v[i];
sort( v, v + N );
g << fixed << setprecision( 10 );
g << DI( 0, N - 1 );
return 0;
}