Cod sursa(job #470734)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 15 iulie 2010 13:33:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long
#define ld long double
#define N_MAX 100005
#define INF 1LL*1<<50
typedef pair <int,int> p;
p X[N_MAX],Y[N_MAX],aux[N_MAX];
int n,i,x,y;

struct cmp
{
	bool operator () (const  p &a,const p &b) const
	{
		return a.first<b.first;
	}
};

inline ll dst(const p &a,const p &b)
{
	ll x=a.first-b.first;
	ll y=a.second-b.second;
	return 1LL*x*x+1LL*y*y;
}

inline ll sqr(int a)
{
	return 1LL*a*a;
}

ll Solve(int st,int dr)
{
	if(st>=dr)
		return INF;
	ll Min=INF;
	if(dr-st<3)
	{
		sort(Y+st,Y+dr+1,cmp());
		for(int i=st;i<dr;i++)
			for(int j=i+1;j<=dr;j++)
				Min=min(Min,dst(X[i],X[j]));
		return Min;
	}

	int md=(st+dr)>>1;

	Min=min(Min,Solve(st,md));
	Min=min(Min,Solve(md+1,dr));

	int i=st,j=md+1,k=0;
	while(i<=md&&j<=dr)
		if(Y[i].first<Y[j].first)
			aux[++k]=Y[i++];
		else
			aux[++k]=Y[j++];
	while(i<=md)
		aux[++k]=Y[i++];
	while(j<=dr)
		aux[++k]=Y[j++];
	for(i=st,k=1;i<=dr;i++,k++)
		Y[i]=aux[k];
	for(i=st,k=0;i<=dr;i++)
		if(sqr(Y[i].second-X[md].first)<=Min)
			aux[++k]=Y[i];
	for(i=1;i<k;i++)
		for(j=i+1;j<=k&&i+7>=j;j++)
			Min=min(Min,dst(aux[i],aux[j]));
	return Min;
}

int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);

	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		X[i]=p(x,y);
	}

	sort(X+1,X+n+1,cmp());

	for(i=1;i<=n;i++)
		Y[i]=p(X[i].second,X[i].first);

	printf("%Lf\n",sqrtl(Solve(1,n)));
	return 0;
}