Cod sursa(job #980659)

Utilizator superman_01Avramescu Cristian superman_01 Data 5 august 2013 13:23:17
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#include<algorithm>
#define oo (1LL<<62)
#define NMAX 1000005
#include<cmath>

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");

struct point
{
	long long x , y ;
	bool operator< (const point a) const
		{
		return (x<a.x);
		}
}v[NMAX];
int N;
point pos[NMAX];
int k = 0 ;

long long real ( long long A )
{
	if( A < 0 )
		return -A ;
	else
		return A;
}
long long dist ( point A , point B )
{
	return real ( ( A.x - B.x) ) *real ( ( A.x -B.x) ) +  real ( ( A.y-B.y ) )  *real ( ( A.y-B.y ) );
}
long long DEI(int st ,int dr)
{
	long long a,b;
	long long x ; 
    int	i , ii;
	int m = (st + dr ) / 2;
	if(st >= dr )
		return oo;
	if( dr-st==1 )
		return dist(v[st],v[dr]);
	a=DEI( st , m ) ;
	b=DEI( m + 1 , dr ) ;
	x=min(a,b);
	k = 0 ;
	for(  i = st ; i <= dr ; ++i )
		if( real(v[m].x - v[i].x) < x )
			pos[++k] = v[i];

	for( i = 1 ; i <= k ; ++i )
      for( ii = i+1  ; ii <= k ; ++ii )
		 x = min(x,dist ( v[i], v[ii] )) ;
	  
	 return x ;
}

int main ( void )
{
	int i ;
	long long Answer ;
	f>>N;
	for( i = 1 ; i <= N ;  ++i )
		f>>v[i].x>>v[i].y;
	sort(v+1,v+N+1) ;
	Answer = DEI(1,N);
	g.precision(7);
	g<<fixed<<sqrtl(Answer ) ;
}