Pagini recente » Cod sursa (job #785527) | Cod sursa (job #1045294) | Cod sursa (job #1776606) | Cod sursa (job #1993306) | Cod sursa (job #580187)
Cod sursa(job #580187)
#include <cmath>
#include <vector>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define INF 9e18
using namespace std;
typedef unsigned long long int llu;
struct point
{
int x, y;
point() : x(0), y(0) {}
point( int _x, int _y ) : x(_x), y(_y) {}
bool operator<( const point& p ) const { return x == p.x ? y < p.y : x < p.x; }
};
vector< point > v;
inline istream& operator>>( istream& in, point& z ) { in>>z.x>>z.y; return in; }
inline llu _min( llu x, llu y ) { return ( x <= y ? x : y ); }
inline int _abs( int x ) { return ( x >= 0 ? x : -x ); }
inline llu D( const point& x, const point& y ) { return 1LL*(x.x-y.x)*(x.x-y.x)+1LL*(x.y-y.y)*(x.y-y.y); }
inline void _swap( point &x, point& y )
{
point aux;
aux=x;
x=y;
y=aux;
}
inline bool cmp( const point& x, const point& y ) { return x.y < y.y; }
inline llu getMinDist( int left, int right )
{
if( left > right )
return INF;
if( left == right )
return 0;
if( 1 == right-left )
return D( v[left], v[right] );
if( 2 == right-left )
return _min( D( v[left], v[left+1] ), _min( D( v[left+1], v[right] ), D( v[left], v[right] ) ) );
int middle=(left+right)>>1, i, j, till;
llu MinD=_min( getMinDist( left, middle ), getMinDist( middle+1, right ) );
vector< point > P;
for( i=left; i <= right; ++i )
if( _abs( v[i].x-v[middle].x ) <= MinD )
P.push_back(v[i]);
sort( P.begin(), P.end(), cmp );
till=P.size();
for( i=0; i < till; ++i )
{
for( j=i+1; j < till && j-i < 8; ++j )
MinD=_min( MinD, D( P[i], P[j] ) );
}
return MinD;
}
int main( void )
{
int N;
ifstream in( "cmap.in" );
in>>N;
copy( istream_iterator<point>(in), istream_iterator<point>(), back_inserter(v) );
sort( v.begin(), v.end() );
ofstream out( "cmap.out" );
out<<fixed<<setprecision(7)<<sqrt((double)getMinDist( 0, N-1 ))<<'\n';
return EXIT_SUCCESS;
}