Cod sursa(job #559389)

Utilizator hadesgamesTache Alexandru hadesgames Data 17 martie 2011 20:00:56
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define pii pair <int,int>
#define x first
#define y second
#define NMAX 100005
#define inf 1LL<<62
using namespace std;
pii a[NMAX];
int n,b[NMAX],r;
inline long long d(int x,int y)
{
	return (long long)(a[x].x-a[y].x)*(a[x].x-a[y].x)+(long long)(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
inline long long min(long long x,long long y)
{
	return x<y ? x : y;
}
long long solve(long long st,long long dr)
{
	if (st==dr)
		return inf;
	if (dr-st==1)
		return d(st,dr);
	int mij=(st+dr)/2;
	long long  rez=min(solve(st,mij),solve(mij+1,dr));
	r=0;
	int i,j;
	for (i=st; i<=mij; i++)
		if (a[mij].x-a[i].x<=rez)
			b[++r]=i;
	for (i=mij+1; i<=dr; i++)
		if (a[i].x-a[mij].x<=rez)
			b[++r]=i;
	for (i=1; i<=r; i++)
		for (j=i+1; j<=r && j-i<8; j++)
			rez=min(rez,d(b[i],b[j]));
	return rez;
}
int main()
{
  long long rez;
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
  scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d%d",&a[i].x,&a[i].y);

	sort(a+1,a+n+1);
	rez=solve(1,n);
	printf("%.7lf\n",sqrt((double)rez));
	return 0;
}