Cod sursa(job #797422)

Utilizator radustn92Radu Stancu radustn92 Data 14 octombrie 2012 00:24:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 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],C[NMAX],D[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);
}
void modif(pii &a,pii &b)
{
	a.x=b.y; a.y=b.x;
}
ll search(int st,int dr)
{
	if (st==dr)
	{
		modif(C[st],A[st]);
		return INF;
	}
	if (dr-st==1)
	{
		if (A[st].y<A[dr].y)
			modif(C[st],A[st]),modif(C[dr],A[dr]);
		else
			modif(C[st],A[dr]),modif(C[dr],A[st]);
		
		return d(A[st],A[dr]);
	}
	int mij=(st+dr)/2;
	ll val=min(search(st,mij),search(mij+1,dr));
	
	merge(C+st,C+mij+1,C+mij+1,C+dr+1,D+st);
	copy(D+st,D+dr+1,C+st);
	
	int i,j;
	m=0;
	for (i=st; i<=dr; i++)
		if ((ll)(C[i].y-A[mij].x)*(C[i].y-A[mij].x)<=val)
			modif(B[++m],C[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);
	int i;
	printf("%.7lf\n",sqrt((double)rez));
	return 0;
}