Cod sursa(job #565599)

Utilizator ilincaSorescu Ilinca ilinca Data 27 martie 2011 22:53:05
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

#define nmax 100015
#define x first
#define y second
#define eps 0.0000001

using namespace std;

typedef pair <int, int> ii;

int n;
ii p [nmax], f [nmax];

void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i <= n; ++i) scanf ("%d%d", &p [i].x, &p [i].y);
	sort (p+1, p+1+n);
}

inline double min (double a, double b)
{
	if (a < b)
		return a;
	return b;
}

inline double dist (ii p1, ii p2)
{
	return sqrt ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

inline double abs (double a)
{
	if (a < 0) return -a;
	return a;
}

bool cmp (ii a, ii b)
{
	if (abs (a.y-b.y) <= eps)
	{
		if (a.x < b.x) return true;
		return false;
	}
	return a.y < b.y;
}

double cmap (int st, int dr)
{
	if (st+1 == dr)
		return dist (p [st], p [dr]);
	if (st+2 == dr)
		return min (min (dist (p [st], p [st+1]), dist (p [st], p [st+2])), dist (p [st+1], p [st+2]));
	int m=(st+dr)/2, i, j, num=0;
	double s=min (cmap (st, m), cmap (m+1, dr));
	for (i=st; i <= dr; ++i)
		if (p [i].x >= p [m].x-s && p [i].x <= p [m].x+s)
			f [++num]=p [i];
	sort (f+1, f+1+num, cmp);
	for (i=1; i <= num; ++i)
		for (j=1; j <= 7; ++j)
		{
			if (i+j > num) continue;
			s=min (s, dist (p [i], p [i+j]));
		}	
	return s;
}

int main ()
{
	freopen ("cmap.in", "r", stdin);
	freopen ("cmap.out", "w", stdout);
	scan ();
	printf ("%lf\n", cmap (1, n));
	return 0;
}