Cod sursa(job #445293)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 23 aprilie 2010 13:51:27
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
#define MAXN 100100
#define x first
#define y second
#define per pair<long long, long long>

using namespace std;

per a[MAXN];
int n,i;

inline long long dist(const per &a, const per &b)
{ return ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); }

long long solve(int st, int dr)
{
	if (st >= dr) return 1000000000000000000LL;
	if (dr-st == 1)
		return dist(a[st],a[dr]);
	int mij = (st+dr)>>1;
	long long best = min(solve(st,mij), solve(mij,dr));
	vector<per > Y;
	for (int i=st; i<=dr; i++)
		if (dist(a[i],a[mij])<=best)
			Y.push_back(a[i]);
	for (int i=0; i<Y.size(); i++)
		for (int j=i+1; j<Y.size() && j-i<=8; j++)
			best = min(best, dist(a[i], a[j]));
	return best;
}
int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++)
		scanf("%lld %lld",&a[i].x, &a[i].y);

	sort(a+1,a+n+1);

	long long solution = solve(1,n);

	printf("%.7lf\n",sqrt((double)solution));

	return 0;
}