Cod sursa(job #530419)

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

struct punct { int 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");
int pdist(punct a, punct b)
{
	return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

int divimp(int st, int dr)		//st, dr = indici
{
	int i,j;
	//cout << st << " " << dr << endl;
	if (dr-st<=2)
		if (dr-st == 1)
		{
			int d = pdist(p[st],p[dr]);
			//cout << d << endl;
			return d;
		}
			
		else
		{
			int d1 = pdist(p[st],p[dr]);
			int d2 = pdist(p[st],p[dr-1]);
			int 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;
		int dst = divimp(st,mj);
		int ddr = divimp(mj+1,dr);
		int 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++)
			{
				int dx = pdist(p[i],p[j]);
				if (dx < d)
					d = dx;
			}
		//cout << st << " " << dr << " " << d << endl;
		return d;
	}
}



int main()
{
	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 << sqrt(rez);
	g.precision(8);
	g << sqrt(rez);
	
	return 0;
}