Cod sursa(job #599238)

Utilizator SmarandaMaria Pandele Smaranda Data 28 iunie 2011 13:20:44
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define inf 2000000000l
#define eps 0.000001
long n;
struct POINT
{
	double x,y;
};
POINT p[100006];
POINT temp[100006];
long part (long st , long dr)
{
	long m,i,j;
	POINT piv,aux;
	m=(st+dr)/2;
	i=st-1;
	j=dr+1;
	piv=p[m];
	while (1)
	{
		do {++i;}while (p[i].x<piv.x || (p[i].x==piv.x && p[i].y<piv.y));
		do {--j;}while (p[j].x>piv.x || (p[i].x==piv.x && p[i].y>piv.y));
		if (i<j)
		{
			aux=p[i];
			p[i]=p[j];
			p[j]=aux;
		}
		else
			return j;
	}
}

void quick (long st , long dr)
{
	long sp;
	if (st<dr)
	{
		sp=part(st,dr);
		quick(st,sp);
		quick(sp+1,dr);
	}
}

long part2 (long st , long dr)
{
	long m,i,j;
	POINT piv,aux;
	m=(st+dr)/2;
	i=st-1;
	j=dr+1;
	piv=temp[m];
	while (1)
	{
		do {++i;}while (temp[i].y<piv.y || (temp[i].y==piv.y && temp[i].x<piv.x));
		do {--j;}while (temp[j].y>piv.y || (temp[i].y==piv.y && temp[i].x>piv.x));
		if (i<j)
		{
			aux=temp[i];
			temp[i]=temp[j];
			temp[j]=aux;
		}
		else
			return j;
	}
}

void quick2 (long st , long dr)
{
	long sp;
	if (st<dr)
	{
		sp=part2(st,dr);
		quick2(st,sp);
		quick2(sp+1,dr);
	}
}

double dist (long st , long dr)
{
	return sqrt ( (p[st].x-p[dr].x)*(p[st].x-p[dr].x) + (p[st].y-p[dr].y)*(p[st].y-p[dr].y) );
}

double minim(double a , double b)
{
	if (a-b<-eps)
		return a;
	else
		return b;
}

double calcul_mediana (long m , double d)
{
	long i,u=0,j;
	double k,min=d;
	memset(temp,0,sizeof(temp));
	for (i=m;i>=1;i--)
	{
		if (p[m].x-d>=p[i].x)
			temp[++u]=p[i];
	}
	for (i=m;i<=n;i++)
	{
		if (p[m].x+d>=p[i].x)
			temp[++u]=p[i];
	}
	quick2(1,u);
	for (i=1;i<=n-6;i++)
		for (j=1;j<=6;j++)
		{
			k=dist(i,i+j);
			if (k-d<-eps)
				if (k-min<-eps)
					min=k;
		}
	return min;
}

double divide (long st  , long dr)
{
	double min1,min2,d,d1;
	long m;
	if (st>=dr)
		return inf;
	if (dr-st+1==2)
		return dist(st,dr);
	m=(st+dr)/2;
	min1=divide(st,m);
	min2=divide(m+1,dr);
	d=minim(min1,min2);
	d1=calcul_mediana(m,d);
	return minim(d,d1);
}

int main()
{
	long i;
	double af;
	
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	
	scanf("%ld",&n);
	for (i=1;i<=n;i++)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	quick(1,n);
	af=divide(1,n);
	printf("%lf\n",af);
	return 0;
}