Cod sursa(job #435118)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 6 aprilie 2010 22:14:13
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 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);B[i]=A[i];}
}
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<=1)return 6000000000.0;
	if(hi-lo==2)
	{
		if(B[lo]>B[lo+1]){Aux=B[lo];B[lo]=B[lo+1];B[lo+1]=Aux;}
		return dist(A[lo],A[lo+1]);
	}
	mi=(lo+hi)>>1;X=A[mi].x;UP=DEI(lo,mi);DOWN=DEI(mi,hi);
	RET=UP<DOWN?UP:DOWN;
	merge(B+lo,B+mi,B+mi,B+hi,C+lo,cmpY);copy(C+lo,C+hi,B+lo);
	for(i=lo,k=0;i<hi;i++)
	{
		if(B[i].x-X>RET)continue;
		if(X-B[i].x>RET)continue;
		C[++k]=B[i];
	}
	for(i=1;i<k;i++)
	{
		p=k<i+7?k:i+7;
		for(j=i+1;j<=p;j++)
		{
			AUX=dist(C[i],C[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));
}
int cmpY(punct U,punct V)
{
	if(U.y<V.y)return 1;
	return 0;
}