Cod sursa(job #565602)

Utilizator ilincaSorescu Ilinca ilinca Data 27 martie 2011 23:07:42
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

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

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 long long min (long long a, long long b)
{
	if (a < b)
		return a;
	return b;
}

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

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

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

long long 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;
	long long s=min (cmap (st, m), cmap (m+1, dr));
	for (i=st; i <= dr; ++i)
		if (abs (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", sqrt (cmap (1, n)));
	return 0;
}