Pagini recente » Cod sursa (job #207267) | Cod sursa (job #2544538) | Cod sursa (job #2981307) | Cod sursa (job #1154187) | Cod sursa (job #580157)
Cod sursa(job #580157)
#include <cmath>
#include <vector>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define INF 9e18
#define N_MAX 100011
using namespace std;
typedef unsigned long long int llu;
struct point
{
int x, y;
int idxY;
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; }
bool operator==( const point& p )const { return y == p.y; }
};
int was[N_MAX];
vector< point > v, v2;
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 _min( int x, int y ) { return ( x <= y ? x : y ); }
inline int _max( int x, int 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 ) );
int min=N_MAX+1, max=-1;
vector< point > P;
for( i=left; i <= right; ++i )
if( _abs( v[i].x-v[middle].x ) <= MinD )
was[v[i].idxY]=i, min=_min( min, v[i].idxY ), max=_max( max, v[i].idxY );
for( ; min <= max; ++min )
if( was[min] )
{
P.push_back( v[was[min]] );
was[min]=0;
}
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) );
v2=v;
sort( v2.begin(), v2.end(), cmp );
for( int i=0; i < N; ++i )
{
v[i].idxY=lower_bound( v2.begin(), v2.end(), v[i] )-v2.begin();
}
sort( v.begin(), v.end() );
ofstream out( "cmap.out" );
out<<fixed<<setprecision(7)<<sqrt((double)getMinDist( 0, N-1 ))<<'\n';
return EXIT_SUCCESS;
}