Pagini recente » Cod sursa (job #1805429) | Cod sursa (job #1289003) | Cod sursa (job #495959) | Cod sursa (job #1797512) | Cod sursa (job #625544)
Cod sursa(job #625544)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define PLL pair< long long, long long >
#define ll long long
#define mp make_pair
#define x first
#define y second
#define xdupay second
#define NMAX 100005
#define INF (1LL<<62)
using namespace std;
PLL X[NMAX], Y[NMAX], Aux[NMAX];
int N, i, j, lg;
ifstream in("cmap.in");
ofstream out("cmap.out");
inline ll Dist( PLL A, PLL B )
{
return ( A.x - B.x )*( A.x - B.x ) + ( A.y - B.y )*( A.y - B.y );
}
inline ll Sol( int St, int Dr )
{
if( St >= Dr-1 ) return INF;
else if( Dr == St + 2 )
{
if( Y[St] > Y[Dr - 1] ) swap( Y[St], Y[Dr - 1] );
return Dist( X[St], X[Dr - 1] );
}
int M = ( St + Dr )/2;
ll DistMin = min( Sol( St, M ), Sol( M, Dr ) );
merge( Y + St, Y + M, Y + M, Y + Dr, Aux );
copy( Aux, Aux + ( Dr - St ), Y + St );
lg = 0;
for( i = St; i < Dr; ++i )
if( abs( X[M].x - Y[i].xdupay ) <= DistMin )
Aux[ lg++ ] = Y[i];
for( i = 0; i < lg - 1; ++i )
for( j = i + 1; j < lg && j - i < 8; ++j )
DistMin = min( DistMin, Dist( Aux[i], Aux[j] ) );
return DistMin;
}
int main()
{
in >> N;
for( i = 0; i < N; ++i )
in >> X[i].x >> X[i].y;
sort( X, X + N );
for( i = 0; i < N; ++i )
Y[i] = mp( X[i].y, X[i].x );
out << fixed << setprecision(6) << sqrt( (double)Sol( 0, N ) ) << '\n';
return 0;
}