Cod sursa(job #584540)

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

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


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


void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)
		scanf("%d %d",&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+1<=3)
	{
		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(int x1,int y1, int x2, int y2)
{
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}


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


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