Pagini recente » Cod sursa (job #700902) | Cod sursa (job #2773173) | Cod sursa (job #654904) | Cod sursa (job #1141450) | Cod sursa (job #1121088)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
const int Nmax = 100002;
const double inf = 1e18;
const double EPS = 1e-10;
struct Point
{
double x, y;
int ind;
Point( double a = 0, double b = 0, int in = -1 )
{
x = a;
y = b;
ind = in;
}
};
struct NOD
{
int ind1, ind2;
double dist;
NOD( int in1 = -1, int in2 = -1, double dist1 = inf )
{
ind1 = in1;
ind2 = in2;
dist = dist1;
}
friend ostream& operator << ( ostream &f, NOD ND )
{
int a = min( ND.ind1, ND.ind2 );
int b = max( ND.ind1, ND.ind2 );
///f << a << " " << b << " ";
f << fixed << setprecision( 10 ) << ND.dist;
return f;
}
};
Point v[Nmax];
int tmp[Nmax];
int N;
double DIST( Point A, Point B )
{
return sqrt( pow( A.x - B.x, 2.0 ) + pow( A.y - B.y, 2.0 ) );
}
bool cmpx( Point A, Point B )
{
return A.x < B.x;
}
bool cmpy( int A, int B )
{
return v[A].y < v[B].y;
}
NOD DI( int st, int dr )
{
if ( st == dr ) return NOD( -1, -1, inf );
if ( st + 1 == dr ) return NOD( v[st].ind, v[dr].ind, DIST( v[st], v[dr] ) );
int m = ( st + dr ) / 2;
NOD d1 = DI( st, m );
NOD d2 = DI( m + 1, dr );
NOD d;
if ( d1.dist > d2.dist )
d = d2;
else
d = d1;
int k = 0;
for ( int i = st; i <= dr; ++i )
{
if ( abs( v[m].x - v[i].x ) <= d.dist )
tmp[ k++ ] = i;
}
sort( tmp, tmp + k, cmpy );
for ( int i = 0; i < k; ++i )
for ( int j = i + 1; j < k && v[ tmp[j] ].y - v[ tmp[i] ].y <= d.dist; ++j )
{
double ddd = DIST( v[ tmp[j] ], v[ tmp[i] ] );
if ( d.dist > ddd )
{
d = NOD( v[ tmp[i] ].ind, v[ tmp[j] ].ind, ddd );
}
}
return d;
}
int main()
{
ifstream cin("cmap.in");
ofstream cout("cmap.out");
cin >> N;
for ( int i = 0; i < N; ++i )
{
cin >> v[i].x >> v[i].y;
v[i].ind = i;
}
sort( v, v + N, cmpx );
cout << DI( 0, N - 1 ) << "\n";
return 0;
}