Cod sursa(job #408248)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 2 martie 2010 22:13:17
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>


using namespace std;

#define file_in "cmap.in"
#define file_out "cmap.out"

#define x first
#define y second

#define pdd pair<double,double>
#define Nmax 122212

struct punct
{
	int x,y;
};


int N;
punct v[Nmax];
punct p[Nmax];


double dist(punct a, punct 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)));
}

int cmp(punct a, punct b)
{
	return ((a.x<b.x) || (a.x==b.x && a.y<b.y));
}

double dmin(int st, int dr)
{
	int mij=(st+dr)>>1;
	int m=p[mij].x;
	if (st>=dr)
		return 100000000.0;
	if (st==dr-1)
	{
		if (p[st].y>p[dr].y)
		{
			punct aux;
			aux=p[st];
			p[st]=p[dr];
			p[dr]=aux;
		}
		return dist(p[st],p[dr]);
	}
	
	double d1=dmin(st,mij);
	double d2=dmin(mij+1,dr);
	double d=min(d1,d2);
	int i1=st;
	int i2=mij+1;
	int i=st-1;

	while(i1<=mij && i2<=dr)
	    if (p[i1].y<=p[i2].y) v[++i]=p[i1++];
		else v[++i]=p[i2++];
	while(i1<=mij) v[++i]=p[i1++];	
	while(i2<=dr) v[++i]=p[i2++];	
	
	int nr=0;
	for(i=st;i<=dr;++i)
	{
		p[i]=v[i];
		if (abs(p[i].x-m)<=d) v[++nr]=p[i];
	}
	
	double q=100000000.0;
	int j;
	for(i=1;i<=nr;++i)
		for(j=i-1;j>=i-7;--j)
			q=min(q,dist(v[i],v[j]));

	return min(q,d);
}

			


int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &N);
	for (int i=1;i<=N;++i)
		 scanf("%d %d", &p[i].x, &p[i].y);
	
	sort(p+1,p+N+1,cmp);
	
	//for (int i=1;i<=N;++i) printf("%d %d\n", p[i].x, p[i].y);
	
	double sol=dmin(1,N);
	printf("%.6lf\n", sol);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}