Cod sursa(job #579796)

Utilizator BitOneSAlexandru BitOne Data 12 aprilie 2011 14:35:32
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <cmath>
#include <vector>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
struct point
{
	int x, y;
	point() : x(1000000001), y(1000000001) {}
	point( int _x, int _y ) : x(_x), y(_y) {}
	bool operator<( const point& z ) const { return ( x == z.x ? y < z.y : x < z.x ); } 
};
vector< point > v;
inline istream& operator>>( istream& in, point& z ) { in>>z.x>>z.y; return in; }
inline double _min( double x, double y ) { return ( x <= y ? x : y ); }
inline double D( const point& p, const point& p2 )
{
	return sqrt( (double)(p.x-p2.x)*(p.x-p2.x)+(double)(p.y-p2.y)*(p.y-p2.y) ) ;
}
int main()
{
	int N, i, j, k;
	double dist=2000000000.00000000;
	ifstream in( "cmap.in" );
	in>>N;
	copy( istream_iterator<point>(in), istream_iterator<point>(), back_inserter(v) );
	sort( v.begin(), v.end() );
	v.push_back( point( (int)dist, (int)dist ) );
	for( i=0; i < N; i=j )
	{
		if( v[i].x != v[i+1].x )
		{
			j=i+1;
			dist=_min( dist, D( v[i], v[i+1] ) );
			continue;
		}
		for( k=i+1; k < N && v[i].x == v[k].x; ++k );
		for( j=i+1; j < N && v[i].x == v[j].x; ++j )
		{
			dist=_min( _min( dist, D( v[j], v[k] ) ), _min( D( v[j-1], v[j] ), D( v[j-1], v[k] ) ) );
		}
	}
	ofstream out( "cmap.out" );
	out<<fixed<<setprecision(7)<<dist<<'\n';
	return EXIT_SUCCESS;
}