Pagini recente » Istoria paginii runda/preoni_nicu4 | Arhiva de probleme | Arhiva de probleme | Documentatie | Cod sursa (job #1121010)
#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-12;
struct Point
{
double x, y;
Point( const double a = 0, const double b = 0 )
{
x = a;
y = b;
}
friend istream& operator >> ( istream &f, Point &P )
{
f >> P.x >> P.y;
return f;
}
friend ostream& operator << ( ostream &f, Point P )
{
f << P.x << " " << P.y;
return f;
}
};
Point v[Nmax];
int 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 cmpy( int A, int B )
{
return v[A].y < v[B].y;
}
bool cmpx( Point A, Point B )
{
return A.x < B.x;
}
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++ ] = i;
}
sort( tmp, tmp + k, cmpy );
double sol = d;
for ( int i = 0; i < k; ++i )
{
for ( int j = i + 1; j < k && v[ tmp[j] ].y - v[ tmp[i] ].y < d; ++j )
{
double dist = DIST( v[ tmp[j] ], v[ tmp[i] ] );
d = min( d, 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, cmpx );
g << fixed << setprecision( 10 );
g << DI( 0, N - 1 );
return 0;
}