Cod sursa(job #599258)

Utilizator SmarandaMaria Pandele Smaranda Data 28 iunie 2011 13:54:33
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.57 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define inf 2000000000l
#define eps 0.000001
long n;
struct POINT
{
	long x;
	long y;
};
POINT p[100009];
POINT temp[100009];
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[j].x==piv.x && p[j].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[j].y==piv.y && temp[j].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 ( (double)(p[st].x-p[dr].x)*(p[st].x-p[dr].x) + (double)(p[st].y-p[dr].y)*(p[st].y-p[dr].y) );
}

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

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

double calcul_mediana (long m , double d , long st ,long dr)
{
	long i,u=0,j;
	double k,min=d;
	memset(temp,0,sizeof(temp));
	for (i=m;i>=st;i--)
	{
		if (p[m].x-d>=p[i].x)
			temp[++u]=p[i];
	}
	for (i=m;i<=dr;i++)
	{
		if (p[m].x+d>=p[i].x)
			temp[++u]=p[i];
	}
	quick2(1,u);
	for (i=1;i<=u;i++)
		for (j=i+1;j<=u && j<=i+6;j++)
		{
			k=dist2(i,j);
			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-st)>>1);
	min1=divide(st,m);
	min2=divide(m+1,dr);
	d=minim(min1,min2);
	d1=calcul_mediana(m,d,st,dr);
	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("%ld%ld",&p[i].x,&p[i].y);
	quick(1,n);
	af=divide(1,n);
	printf("%lf\n",af);
	return 0;
}