Cod sursa(job #797417)

Utilizator radustn92Radu Stancu radustn92 Data 13 octombrie 2012 23:57:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 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,p1,p2,p;
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);
}
ll search(int st,int dr)
{
	if (st==dr)
	{
		C[st]=A[st];
		return INF;
	}
	if (dr-st==1)
	{
		if (A[st].y<A[dr].y)
			C[st]=A[st],C[st+1]=A[dr];
		else
			C[st]=A[dr],C[st+1]=A[st];
		
		return d(A[st],A[dr]);
	}
	int mij=(st+dr)/2;
	ll val=min(search(st,mij),search(mij+1,dr));
	
	p1=st; p2=mij+1; p=st;
	while (p1<=mij && p2<=dr)
	{
		if (C[p1].y<C[p2].y)
			D[p]=C[p1],p1++,p++;
		else
			D[p]=C[p2],p2++,p++;
	}
	while (p1<=mij)
		D[p]=C[p1],p1++,p++;
	while (p2<=dr)
		D[p]=C[p2],p2++,p++;
	for (p=st; p<=dr; p++)
		C[p]=D[p];
	
	int i,j;
	m=0;
	for (i=st; i<=dr; i++)
		if ((ll)(C[i].x-A[mij].x)*(C[i].x-A[mij].x)<=val)
			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);
	printf("%.7lf\n",sqrt((double)rez));
	return 0;
}