Cod sursa(job #435148)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 6 aprilie 2010 22:41:14
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<cstdio>
#include<utility>
#include<algorithm>
#include<cmath>
#define mp make_pair
#define x first
#define y second
#define punct pair<double,double>
using namespace std;
punct A[100010],B[100010],C[100010];
int n,cmpY(punct U,punct V);
double DEI(int lo, int hi),dist(punct U, punct V);
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	double X,Y;int i;
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++){scanf("%lf%lf",&X,&Y);A[i]=mp(X,Y);}
}
void solve()
{
	sort(A+1,A+n+1);
	printf("%.6lf",DEI(1,n+1));
}
double DEI(int lo, int hi)
{
	double RET,AUX,UP,DOWN,X;
	int i,j,k,p,mi;
	punct Aux;
	if(hi==lo)return 60000000000.0;
	if(hi-lo==1)return dist(A[lo],A[hi]);
	mi=(lo+hi)>>1;X=A[mi].x;UP=DEI(lo,mi);DOWN=DEI(mi,hi);
	RET=UP<=DOWN?UP:DOWN;
	for(i=lo,k=0;i<hi;i++)
	{
		if(A[i].x-X>RET)continue;
		if(X-A[i].x>RET)continue;
		B[++k]=A[i];
	}
	for(i=1;i<=k;i++)
	{
		p=k<=i+7?k:i+7;
		for(j=i+1;j<=p;j++)
		{
			AUX=dist(B[i],B[j]);
			RET=RET<=AUX?RET:AUX;
		}
	}
	return RET;
}
double dist(punct U, punct V)
{
	return sqrt((U.x-V.x)*(U.x-V.x)+(U.y-V.y)*(U.y-V.y));
}