Cod sursa(job #1160360)

Utilizator federerUAIC-Padurariu-Cristian federer Data 30 martie 2014 14:47:03
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define Inf 10000000
#define Nmax 10001
using namespace std;
struct Point{
	double x, y;
};
Point Puncte[Nmax];

int N,i;

double _distance(Point A, Point B)
{
	return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}

bool cmp(const Point& A, const Point& B)
{
	if (A.x <= B.x)
		return true;
	return false;
}

bool cmp2(const Point& A, const Point& B)
{
	if (A.y <= B.y)
		return true;
	return false;
}

double solve(int st, int dr)
{
	if (dr - st + 1 <= 3)
	{
		int i, j;
		double d = Inf;
		for (i = st; i <= dr;++i)
		for (j = st; j <= dr; ++j)
		if (i!=j)
		{
			double tmp = _distance(Puncte[i], Puncte[j]);
			d = min(d, tmp);
		}
		return d;
	} 
	else
	{
		int m = (st + dr) / 2, k = 0;
		Point A[Nmax];
		double D1 = solve(st, m);
		double D2 = solve(m + 1, dr);
		double D = min(D1, D2), drp = (Puncte[m].x + Puncte[m + 1].x)/2;
		i = m;
		while (i >= 1 && Puncte[i].x >= drp - D)
		{
			A[k++] = Puncte[i--];
		}
		i = m + 1;
		while (i <=dr && Puncte[i].x <= drp + D)
		{
			A[k++] = Puncte[i++];
		}
		sort(A + 1, A + 1 + k, cmp2);
		for (int i = 1; i <= k;++i)
		for (int j = i + 1; j <= min(k,i + 7); ++j)
			D = min(D, _distance(Puncte[i], Puncte[j]));
		return D;
	}
}

int main()
{
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);
	scanf("%d", &N);
	for (i = 1; i <= N; ++i)
		scanf("%lf %lf", &Puncte[i].x, &Puncte[i].y);
	sort(Puncte + 1, Puncte + N + 1, cmp);
	double rez = solve(1, N);
	printf("%.6lf\n", rez);
	return 0;
}