Cod sursa(job #579888)

Utilizator BitOneSAlexandru BitOne Data 12 aprilie 2011 15:56:09
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <cmath>
#include <vector>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define INF (unsigned long long int)999999999999999999

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 && i-j < 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;
}