Cod sursa(job #797413)

Utilizator radustn92Radu Stancu radustn92 Data 13 octombrie 2012 23:36:14
Problema Cele mai apropiate puncte din plan Scor 80
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 ll long long
#define NMAX 100005
#define INF (1LL<<62)
using namespace std;
int n,m;
pii A[NMAX],B[NMAX];
ll rez;
void read()
{
	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);
}
inline ll min(ll x,ll y)
{
	return x<y ? x : y;
}
inline ll d(pii a,pii b)
{
	return (ll)(a.x-b.x)*(a.x-b.x)+(ll)(a.y-b.y)*(a.y-b.y);
}
inline ll modul(ll x)
{
	return x<0 ? -x : x;
}
ll search(int st,int dr)
{
	if (st==dr)
		return INF;
	if (dr-st==1)
		return d(A[st],A[dr]);
	int mij=(st+dr)/2;
	ll val;
	val=min(search(st,mij),search(mij+1,dr));
	
	int i,j;
	m=0;
	for (i=st; i<=dr; i++)
		if (modul(A[i].x-val)<=val)
			B[++m]=A[i];
		
	for (i=1; i<=m; i++)
		for (j=i+1; j-i<8 && j<=m; j++)
			val=min(val,d(B[i],B[j]));
	return val;
}
int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	read();
	rez=search(1,n);
	printf("%lf\n",sqrt(rez));
	return 0;
}