Cod sursa(job #749808)

Utilizator Theorytheo .c Theory Data 18 mai 2012 21:56:15
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include<fstream>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#include<iomanip>
#define nmax 100005
#define inf 1000000
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Punct{ int x;int y;
	inline void get()
	{
		fin >>x>>y;
	}
	inline void getout()
	{
		fout <<x <<" " << y <<'\n'; 
	}
	inline bool operator< (const Punct& P) const
	{
		return x < P.x || (x ==	P.x && y <P.y);
	}
};
Punct v[nmax], dreapta[nmax], stanga[nmax];
int i, j , n, m, nr, t;
double D = inf;
int sizeA, sizeB;
inline double dist(Punct, Punct);

int bs(Punct b[], int sizeB, double x)
{
	int step = 1 << 16, i;
	for(i = 1; step ;step >>= 1)
		if(i + step <= sizeB && b[i + step].y <= x )
			i += step;
	return i;
}
inline bool cmp( const Punct &a,const  Punct &b)
{
	return a.y < b.y;
}
double join(Punct a[], Punct b[], double D)
{
	int i, st, dr;
	double	rez = D;
	sort(b + 1, b + 1 + sizeB,cmp);
	for(i = 1; i <= sizeA; ++i)
	{
		st = bs(b, sizeB, a[i].y -D);
		dr = bs(b, sizeB, a[i].y +D);
		for(int j = st;  j <= dr; j++)
			rez = min(rez,dist(a[i],b[j]));
	}
	//fout <<rez <<'\n'; 
	return rez;
}
inline int sp(int x)
{
	return x*x;
}
inline double dist(Punct a, Punct b)
{
	return sqrt((double)sp(abs(a.x- b.x)) + sp( abs( (a.y- b.y) ) ));
}
void read()
{
	fin >> n;
	for(int i = 1; i <= n ; ++i)
	{
		v[i].get();
	}
	//fout<<min(v[1].x, v[2].x);
	
	sort( v + 1 , v + 1 + n );
	
	
}
double cmap(int st, int dr)
{
	int m = (st + dr)/ 2;
	if(dr <= st)
		return inf;
	D = min( cmap(st, m), cmap(m + 1, dr) );
	sizeA= sizeB = 0;
	for(int i = st; i <= m; ++i)
	
		if(v[m].x - v[i].x < D)
			stanga[++sizeA] = v[i];
		
	for(int i = m + 1; i <= dr; ++i)
	{
		if(v[i].x - v[m].x < D )
			dreapta[++sizeB] = v[i];
	}
	//fout << st << " " << dr << "  " << D <<'\n';  
	if(!sizeA||!sizeB )
		return D;
	return join(stanga, dreapta, D);
}
int main()
{ 
	read();
	fout<< fixed;
	fout << setprecision(6) << cmap( 1, n);
	fin.close();
	fout.close();
	return 0;
}