Cod sursa(job #599277)

Utilizator elfusFlorin Chirica elfus Data 28 iunie 2011 14:11:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define pb push_back
#include<math.h>
#define LMAX 100100
#define INF 1<<30

using namespace std;

struct pozdy
{
	int x,y;
} x[LMAX];

inline bool comp1(pozdy A,pozdy B)
{
	return A.x<B.x;
}

inline bool comp2(pozdy A,pozdy B)
{
	return A.y<B.y;
}

double dist(pozdy A,pozdy B)
{
	return sqrt((double)((long long)((long long)A.x-B.x)*(A.x-B.x)+(long long)((long long)A.y-B.y)*(A.y-B.y)));
}

double divide(int st,int dr)
{
	if(st>=dr)
		return INF;
	if(dr-st==1)
		return dist(x[st],x[dr]);
	int m=(st+dr)>>1;
	double d1=divide(st,m),d2=divide(m+1,dr),D;
	if(d1<d2)
		D=d1;
	else
		D=d2;
	vector<pozdy> X;
	int i=m,j;
	while(x[m].x-x[i].x<=D && i>=st)
		X.pb(x[i]),i--;
	i=m+1;
	while(x[i].x-x[m].x<=D && i<=dr)
		X.pb(x[i]),i++;
	sort(X.begin(),X.end(),comp2);
	int l=X.size();
	for(i=0;i<l;i++)
		for(j=i+1;j<l && j-i<=6;j++)
			if(dist(X[i],X[j])<D)
				D=dist(X[i],X[j]);
	return D;
}

int main()
{
	int n,i;
	double D;
	
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=n;i++)
		scanf("%d%d",&x[i].x,&x[i].y);
	sort(x+1,x+n+1,comp1);
	D=divide(1,n);
	printf("%.6lf",D);
	return 0;
}