Cod sursa(job #411670)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 5 martie 2010 02:10:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
#define ll long long
#define INF 1LL<<60
#define NMAX 100005
#define x first
#define y second
typedef pair <int,int> p;
p a[NMAX];
int mg[NMAX];
int n,i;
inline ll dst(int i,int j)
{
	return 1LL*(a[i].x-a[j].x)*(a[i].x-a[j].x)+
		1LL*(a[i].y-a[j].y)*(a[i].y-a[j].y);
}
inline bool cmp(const p &a,const p &b)
{
	return a.x<b.x||a.x==b.x&&a.y<b.y;
}
ll solve(int st,int dr)
{
	ll Min=INF,Min1;
	long double MIN;
	int mj=(st+dr)>>1;
	int i,j,k;
	if(dr-st<3)
	{
		for(i=st;i<dr;i++)
			for(j=i+1;j<=dr;j++)
				Min=min(Min,dst(i,j));
		return Min;
	}
	Min=solve(st,mj);
	Min1=solve(mj+1,dr);
	Min=min(Min,Min1);
	MIN=sqrtl(Min);
	for(i=st;i<=dr;i++)
		if(a[mj].x-a[i].x<=MIN)
			break;
	j=mj+1;k=0;
	while(i<=mj&&j<=dr&&a[j].x-a[mj].x<=MIN)
		if(a[i].y<a[j].y)
			mg[++k]=i++;
		else
			mg[++k]=j++;
	while(i<mj)
		mg[++k]=i++;
	while(j<=dr&&a[j].x-a[mj].x<=MIN)
		mg[++k]=j++;
	for(i=1;i<k;i++)
		for(j=i+1;j<=k&&j<=i+7;j++)
			Min=min(Min,dst(mg[i],mg[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",&a[i].x,&a[i].y);
	sort(a+1,a+n+1,cmp);
	printf("%Lf\n",sqrtl(solve(1,n)));
	return 0;
}