Cod sursa(job #432530)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 2 aprilie 2010 14:53:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define Nmax 100005
#define INF 2000000000
using namespace std;

struct punct{ int x,y; } ;
punct a[Nmax];

int n,i;

int cmp(punct a, punct b){
	return (a.x < b.x || (a.x==b.x && a.y<b.y));
}
inline double Minim( double x, double y){
	return x<y ? x:y;
}
inline double abs( double x ){
	return x > 0 ? x : -x; 
}

inline double dist( int i,int j ){
	return sqrt( (double) (a[i].x-a[j].x)*(a[i].x-a[j].x) 
		+ (double) (a[i].y-a[j].y)*(a[i].y-a[j].y) );
}

int aux[Nmax];
double dist_min(int st,int dr){
	double d,d1,d2;
	int i,j,mij;
	
	if(st>=dr) return INF;
	if(st==dr-1)
		return dist(st,dr);
	
	mij=st+(dr-st)/2;
	d1=dist_min(st,mij);
	d2=dist_min(mij+1,dr);
	d=d1 < d2 ? d1 : d2;
		
	aux[0]=0;
	for(i=st;i<=dr;++i)
		if( abs(a[i].x-a[mij].x) <= d )
			aux[++aux[0]]=i;
	
	for(i=1;i<=aux[0];++i)
		for(j=i-1; j>=i-7 && j>0; --j)
			d=Minim(d, dist(aux[i],aux[j]) );
	
	return d;
}

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