Cod sursa(job #579423)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 12 aprilie 2011 09:37:40
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#define DIM 100005
#define OO ((1LL<<61)-1)
#define minim(a,b) (a<b?a:b)
ifstream fi("cmap.in");
ofstream fo("cmap.out");

int N;
struct pct { int x, y; } P[DIM], M[DIM];

int cmp(pct a, pct b)
{
	return a.x < b.x;
}

long long pit(pct a, pct b)
{
	long long x = a.x - b.x;
	long long y = a.y - b.y;
	return x*x + y*y;
}

void merge(int st, int m, int dr)
{
	int i = st, j = m+1, k = 0;
	while (i <= m && j <= dr)
		if (P[i].y < P[j].y)
			M[++k] = P[i++];
		else
			M[++k] = P[j++];
	while (i <= m)
		M[++k] = P[i++];
	while (j <= dr)
		M[++k] = P[j++];
	for (i = st; i <= dr; i++)
		P[i] = M[i-st+1]; 
}

void cit()
{
	fi >> N;
	for (int i = 1; i <= N; i++)
		fi >> P[i].x >> P[i].y;
	sort(P + 1, P + N + 1, cmp);
}

long long die(int st, int dr)
{
	if (st >= dr)
		return OO;
	if (st + 1 == dr)
	{
		if (P[st].y > P[dr].y)
		{
			pct aux = P[st];
			P[st] = P[dr];
			P[dr] = aux;
		}
		return pit(P[st], P[dr]);
	}
	int m = st + dr >> 1;
	pct V = P[m]; 	
	long long s = minim(die(st, m), die(m+1, dr)), d;
	
	merge(st, m, dr);
	
	int i, j, k = 0;
	for (i = st; i <= dr; i++)
		//if (pit(V, P[i]) <= s)
		if (abs (V.x - P[i].x) <= s)
			M[++k] = P[i];
	
	for (i = 1; i <= k; i++)
		for (j = i + 1; j <= i + 7 && j <= k; j++)
		{
			d = pit(M[i], M[j]);
			s = s < d ? s : d;
		}
	return s;
}

void afs()
{
	double d = sqrt((double)die(1, N));
/*
	d *= 10000000;
	if ((int)d % 10 >= 5) d += 10;
	d /= 10000000;	
*/
	fo << setprecision(25) << d;	
}

int main()
{
	cit();
	
	afs();
	
	return 0;
}