Cod sursa(job #715341)

Utilizator Theorytheo .c Theory Data 17 martie 2012 00:55:24
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<stdio.h>
#define nmax 100002
#define inf 100000000
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct Punct {int x ; int y;} ;
Punct v[ nmax ], P[ nmax ] ;
int i ,j, n;
bool cmp(Punct,Punct);
long long min(long long a,long long b)
{
	if(a>b)
		return b;
	return a;
}
inline long long dist( Punct a, Punct b)
{
	return labs((long long)(a.x - b.x) * (a.x - b.x)) + abs((a.y - b.y) * (a.y - b.y)) ;
}
long long divide(int F, int L)
{
	long long dmin = 0 ;
	long long aux = 0;
	if(F>=L)
		return inf;
	
	if(L - F == 1)
		return dist(v[ F ] , v[ L ]);
	if(L - F == 2)
		return min( dist(v[F], v[F + 1]),dist( v[F + 1] ,v[L]) );
	
	
	int m = (F + L) / 2;
	int nr = 0; 
	dmin = min ( divide(F, m), divide( m + 1, L) );
	
	for( i = F; i <= L ; ++i)
	{
		if( abs(v[i].x - v[m].x) <=dmin )
			P[ ++nr ] = v[i] ;
	}
	
	sort(P + 1, P + nr + 1,cmp);
	
	for(i = 1; i <= nr; i++)
	{
		for(j = i + 1; j <= nr; j++)
		{
			aux = dist(P[i] , P[j]);
			if(aux < dmin)
				dmin = aux ; 
			
		}
	}
	return dmin ; 

		
}
bool cmp(Punct a,Punct b)
{
	if(a.x != b.x)
		return a.x < b.x ;
	else
		return a.y < b.y ;
		
}
void read()
{
	
	fin >> n ;
	for( i = 1; i <= n; ++i )
		fin>> v[i].x >> v[i].y ;
	sort(v + 1, v + 1 + n, cmp);
	fout << fixed ;
	fout << setprecision(6) << sqrt((double) divide(1 , n)) << '\n' ;
	
}
int main()
{
	read();
	fin.close();
	fout.close();
	return 0;
}