Cod sursa(job #412449)

Utilizator AndreyPAndrei Poenaru AndreyP Data 5 martie 2010 17:49:53
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define fs first
#define sc second
#define pll pair<long long,long long>
#define mp make_pair
#define ll long long
#define N 100010
int n;
pll x[N],y[N],v[N];
inline ll dist(const pll &x,const pll &y)
{
	return (x.fs-y.fs)*(x.fs-y.fs)+(x.sc-y.sc)*(x.sc-y.sc);
}
inline void citire()
{
	scanf("%d",&n);
	int a1,a2;
	for(int i=1; i<=n; ++i)
	{
		scanf("%d%d",&a1,&a2);
		x[i].fs=(ll)a1;
		x[i].sc=(ll)a2;
		//scanf("%lld",&x[i].fs,&x[i].sc);
	}
	sort(x+1,x+n+1);
	for(int i=1; i<=n; ++i)
		y[i]=mp(x[i].sc,x[i].fs);
}
inline ll minim(ll x,ll y)
{
	if(x<y)
		return x;
	return y;
}
inline ll modul(ll x)
{
	if(x<0)
		return -x;
	return x;
}
ll rezolva(int st,int dr)
{
	if(st>=dr)
		return (1LL<<62);
	if(st+1==dr)
	{
		if(y[st]>y[dr])
			swap(y[st],y[dr]);
		return dist(x[st],x[dr]);
	}
	
	int m=(st+dr)>>1;
	ll rez=minim(rezolva(st,m),rezolva(m+1,dr));
	merge(y+st,y+m+1,y+m+1,y+dr+1,v);
	copy(v,v+(dr-st+1),y+st);
	
	int lim=0;
	for(int i=st; i<=dr; ++i)
	{
		if(modul(y[i].sc-x[m].fs)<=rez)
			v[++lim]=y[i];
	}
	
	int j1;
	for(int i=1; i<lim; ++i)
	{
		j1=lim+1;
		if(j1>i+8)
			j1=i+8;
		for(int j=i+1; j<j1; ++j)
			rez=minim(rez,dist(v[i],v[j]));
	}
	
	return rez;
}
int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	
	citire();
	ll rez=rezolva(1,n);
	printf("%lf\n",sqrt((double)rez));
	
	return 0;
}