Cod sursa(job #757437)

Utilizator vlad.maneaVlad Manea vlad.manea Data 12 iunie 2012 01:40:27
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include <cstdio>
#include <vector>
#include <limits>
#include <algorithm>
#include <cmath>
using namespace std;

int N;
vector< pair<double, double> > P;

inline double dist(int i, int j)
{
	return sqrtl(pow(P[i].first - P[j].first, 2) + pow(P[i].second - P[j].second, 2));
}

double mind(int i, int j)
{
	double a = numeric_limits<double>::max(), d;

	if (j - i <= 2)
	{
		for (int l = i; l < j; ++l)
		{
			for (int m = l + 1; m <= j; ++m)
			{
				d = dist(l, m);
				a = d < a - numeric_limits<double>::epsilon()? d: a;
			}
		}

		vector< pair<double, double> > X;

		for (int l = i; l <= j; ++l)
		{
			X.push_back(make_pair(P[l].second, P[l].first));
		}

		sort(X.begin(), X.end());

		for (int l = 0; l <= j - i; ++l)
		{
			P[l + i].first = X[l].second;
			P[l + i].second = X[l].first;
		}

		return a;
	}

	int l, m, t = (i + j) / 2;
	d = (P[t].first + P[t + 1].first) / 2;

	double left = mind(i, t);
	double rite = mind(t + 1, j);
	double s = left < rite - numeric_limits<double>::epsilon()? left: rite;
	vector< pair<double, double> > X;

	for (l = i, m = t + 1; l <= t && m <= j;)
	{
		if (P[l].second < P[m].second - numeric_limits<double>::epsilon())
		{
			X.push_back(make_pair(P[l].first, P[l].second));
			++l;
		}
		else
		{
			X.push_back(make_pair(P[m].first, P[m].second));
			++m;
		}
	}

	while (l <= t)
	{
		X.push_back(make_pair(P[l].first, P[l].second));
		++l;
	}

	while (m <= j)
	{
			X.push_back(make_pair(P[m].first, P[m].second));
			++m;
	}

	vector< pair<double, double> > Y;

	for (t = 0; t <= j - i; ++t)
	{
		P[t + i].first = X[t].first;
		P[t + i].second = X[t].second;

		if (fabs(X[t].first - d) < s + numeric_limits<double>::epsilon())
		{
			Y.push_back(make_pair(X[t].first, X[t].second));
		}
	}

	t = Y.size();

	for (l = 0; l < t; ++l)
	{
		for (m = l + 1; m < l + 8 && m < t; ++m)
		{
			d = dist(l, m);
			a = d < a - numeric_limits<double>::epsilon()? d: a;
		}
	}

	return a < s - numeric_limits<double>::epsilon()? a: s;
}


int main()
{
	int i;
	double x, y;
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);
	scanf("%d", &N);

	for (i = 0; i < N; ++i)
	{
		scanf("%lf%lf", &x, &y);
		P.push_back(make_pair(x, y));
	}

	sort(P.begin(), P.end());
	printf("%lf\n", mind(0, N - 1));
	return 0;
}