Cod sursa(job #749812)

Utilizator Theorytheo .c Theory Data 18 mai 2012 22:55:31
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include<iomanip.h>
#include <algorithm>
#define nmax 100005
#define inf 3e10
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 n;

int sizeA, sizeB;
inline double dist(Punct, Punct);

double min(double a, double b)
{
	return a > b ? b : a;
}
int bs(Punct f[], int n, double x)
{
	int step = 1 << 16, i;
	for(i = 1; step ;step >>= 1)
		if(i + step <= n && f[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 double sp(double x)
{
	return x*x;
}
inline double dist(Punct A, Punct B)
{
	return sqrt(sp(A.x- B.x) + sp( (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)
{
	if(dr <= st)
		return inf;
	int m = (st + dr)>> 1;
	
	double 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;
}