Cod sursa(job #579391)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 12 aprilie 2011 09:10:19
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
#define DIM 100005
#define OO (1<<31) - 1

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;
	long long s = min(die(st, m), die(m+1, dr)), d;
	pct V = P[m]; 
	merge(st, m, dr);
	
	int i, j, k = 0;
	for (i = st; i <= dr; i++)
		if (pit(V, P[i]) <= 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;
}

int main()
{
	cit();
	
	fo << setprecision(8) << sqrt((double)die(1, N));
	
	return 0;
}