Cod sursa(job #468686)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 4 iulie 2010 17:09:45
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define pii pair <int,int>
#define x first
#define y second
#define ll long long 
#define NMAX 100005
#define INF 1LL<<62
using namespace std;
pii A[NMAX];
int n,B[NMAX],r;
ll rez;
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d%d",&A[i].x,&A[i].y);
}
inline ll d(int a,int b)
{
	return (ll)(A[a].x-A[b].x)*(A[a].x-A[b].x)+(ll)(A[a].y-A[b].y)*(A[a].y-A[b].y);
}
inline ll min(ll x,ll y)
{
	return x<y ? x : y;
}
ll solve(int st,int dr)
{
	if (st==dr)
		return INF;
	if (dr-st==1)
		return d(st,dr);
	int mij=(st+dr)/2;
	ll best=min(solve(st,mij),solve(mij+1,dr));
	r=0;
	int i,j;
	for (i=st; i<=mij; i++)
		if (A[mij].x-A[i].x<=best)
			B[++r]=i;
	for (i=mij+1; i<=dr; i++)
		if (A[i].x-A[mij].x<=best)
			B[++r]=i;
	for (i=1; i<=r; i++)
		for (j=i+1; j<=r && j-i<8; j++)
			best=min(best,d(B[i],B[j]));
	return best;
}
int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	read();
	sort(A+1,A+n+1);
	rez=solve(1,n);
	printf("%.7lf\n",sqrt((double)rez));
	return 0;
}