Cod sursa(job #584542)

Utilizator balakraz94abcd efgh balakraz94 Data 25 aprilie 2011 21:25:09
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define infile "cmap.in"
#define outfile "cmap.out"
#define min(a,b) a<b ? a : b
#define L 100005
#define INF 2000000005
typedef long long i64;
using namespace std;

void citeste();
double rezolva(int,int);
void afiseaza();
double euclid(i64,i64,i64,i64);


struct punct {i64 x,y;};
punct a[L];
int n;


void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
		scanf("%lld %lld",&a[i].x, &a[i].y);

	fclose(stdin);
}


int mycmp(punct a, punct b)
{
	if(a.x!=b.x)
		return a.x<b.x;
	return a.y<b.y;
}


double rezolva(int p, int q)
{
	if(p>=q) 
		return INF;
	
	if(q-p==1)
		return euclid(a[p].x,a[p].y,a[q].x,a[q].y);
	
	if(q-p==2)
	{
		double d1,d2,d3,dmin;
		
		d1 = euclid(a[p].x,a[p].y,a[p+1].x,a[p+1].y);
		
		d2 = euclid(a[p].x,a[p].y,a[q].x,a[q].y);
		
		dmin = min(d1,d2);
		
		d3 = euclid(a[p+1].x,a[p+1].y,a[q].x,a[q].y);
		
		dmin = min(dmin,d3);
	}
	
	return min(rezolva(p,(p+q)/2),rezolva((p+q)/2+1,q));
}


double euclid(i64 x1,i64 y1, i64 x2, i64 y2)
{
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}


void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%f\n",rezolva(1,n));
	
	fclose(stdout);
}


int main()
{
	citeste();
	
	sort(a+1,a+n+1,mycmp);
	
	afiseaza();
	
	return 0;
}