Cod sursa(job #481787)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 1 septembrie 2010 18:04:30
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

const int NMAX=100005;

#define x first
#define y second

typedef pair<int,int> punct;

double dist(punct A, punct B)
{
	double dx=A.x-B.x, dy=A.y-B.y;
	return sqrt(dx*dx + dy*dy);
}

punct P[NMAX],Y[NMAX],Z[NMAX];

double solve(int l,int r)
{
	if (r-l+1 <= 3)
	{
		double dmin=1e10;
		for (int i=l;i<r;++i)
			for (int j=i+1;j<=r;++j)
				dmin=min(dmin, dist(P[i], P[j]));
		sort(Y+l,Y+r+1);
		return dmin;
	}

	int m=(l+r)/2;
	double dmin=min(solve(l,m), solve(m+1,r));
	merge(Y+l,Y+m+1,Y+m+1,Y+r+1,Z);
	copy(Z,Z+r-l+1,Y+l);
	int len=0;
	for (int i=l;i<=r;++i)
		if (abs(Y[i].y - P[m].x) <= dmin)
			Z[++len]=Y[i];

	for (int i=2;i<=len;++i)
		for (int j=i-1;j>=1 && i-j<=7;--j)
			dmin=min(dmin, dist(Z[i], Z[j]));

	return dmin;
}

int N;

int main()
{
	ifstream fin("cmap.in");
	fin>>N;
	for (int i=1;i<=N;++i) fin>>P[i].x>>P[i].y;
	sort(P+1,P+N+1);
	for (int i=1;i<=N;++i) Y[i]=make_pair(P[i].y, P[i].x);

	freopen("cmap.out","w",stdout);
	printf("%lf\n",solve(1,N));

	return 0;
}