Cod sursa(job #530425)

Utilizator Raul_NistorNistor Raul Raul_Nistor Data 7 februarie 2011 19:31:14
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <math.h>
#define NMAX 100001
using namespace std;

struct punct { long double x,y;};

int cmp(punct a, punct b)
{
	if (a.x<=b.x) return 1;
	else return 0;
}

punct p[NMAX];
int  n,i;

ifstream f("cmap.in");
ofstream g("cmap.out");
long double pdist(punct a, punct b)
{
	return sqrtl((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

long double divimp(int st, int dr)		//st, dr = indici
{
	int i,j;
	//cout << st << " " << dr << endl;
	if (dr-st<=2)
		if (dr-st == 1)
		{
			long double d = pdist(p[st],p[dr]);
			//cout << d << endl;
			return d;
		}
			
		else
		{
			long double d1,d2,d3;
			 d1 = pdist(p[st],p[dr]);
			 d2 = pdist(p[st],p[dr-1]);
			 d3 = pdist(p[st+1],p[dr]);
			//cout << st << " " << dr << " " << d1 << " " << d2 << " " << d3 << " " << endl;
			if (d1 <= d2 && d1 <= d3) return d1;
			if (d2 <= d1 && d2 <= d3) return d2;
			return d3;
		}
	else
	{
		int mj = (st+dr)/2;
		long double dst = divimp(st,mj);
		long double ddr = divimp(mj+1,dr);
		long double d = min(dst,ddr);
		for (i=mj-1;i>=0;i--)
			if (p[mj].x - p[i].x > d)
				break;
		int limst = i+1;
		for (i=mj+1;i<n;i++)
			if (p[i].x - p[mj].x > d)
				break;
		int limdr = i-1;
		//cout << d << " " << limst << " " << limdr << endl;
		for (i=limst;i<=mj;i++)
			for (j=mj+1;j<=limdr;j++)
			{
				long double dx = pdist(p[i],p[j]);
				if (dx < d)
					d = dx;
			}
		//cout << st << " " << dr << " " << d << endl;
		return d;
	}
}



int main()
{
	long double rez;
	f >> n;
	for (i=0;i<n;i++)
		f>>p[i].x>>p[i].y;
	
	sort(p,p+n,cmp);
	
	rez = divimp(0,n-1);
	cout.precision(8);
	cout << rez;
	g.precision(8);
	g << rez;
	
	return 0;
}