Cod sursa(job #565624)

Utilizator ilincaSorescu Ilinca ilinca Data 28 martie 2011 00:28:04
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

#define nmax 100015
#define x first
#define y second
#define inf (long long)1000000000000000000
#define eps 0.0000000001

using namespace std;

typedef pair <int, int> ii;

int n;
ii p [nmax], f [nmax], v [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);
	for (i=1; i <= n; ++i) v [i]=p [i];
}

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 1LL*(p1.x-p2.x)*(p1.x-p2.x)+1LL*(p1.y-p2.y)*(p1.y-p2.y);
}

inline void merge (int st, int dr)
{
	int m=(st+dr)/2, i1=st, i2=m+1, num=0;
	while (i1 <= m && i2 <= dr)
	{
		if (p [i1].y <= p [i2].y)
			f [++num]=p [i1++];
		else
			f [++num]=p [i2++];
	}
	for (; i1 <= m; ++i1) f [++num]=p [i1];
	for (; i2 <= dr; ++i2) f [++num]=p [i2];
	for (i1=1; i1 <= num; ++i1)
		p [st+i1-1]=f [i1];
}

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

long long cmap (int st, int dr)
{
	if (st >= dr) 
		return inf;
	if (st+1 == dr)
	{
		if (p [st].y > p [dr].y)
		{
			ii aux=p [st];
			p [st]=p [dr];
			p [dr]=aux;
		}
		return dist (p [st], p [dr]);
	}
	int m=(st+dr)/2, i, j, num=0;
	long long s=min (cmap (st, m), cmap (m+1, dr));
	merge (st, dr);
//	for (i=st; i <= dr; ++i) fprintf (stderr, "(%d %d) ", p [i].x, p [i].y);
//	fprintf (stderr, "\n\n\n");
	for (i=st; i <= dr; ++i)
		if (abs (p [i].x-v [m].x) <= s)
			f [++num]=p [i];
	for (i=1; i <= num; ++i)
		for (j=1; j <= 7; ++j)
		{
			if (i+j > num) continue;
			s=min (s, dist (f [i], f [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;
}