Cod sursa(job #408019)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 2 martie 2010 19:56:14
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>

using namespace std;

#define nmax 100001

struct punct { int x,y;};

punct v[nmax];
int n;

double cmp(punct p1, punct p2)
{
	return p1.x<=p2.x;
}
double dist (punct p1, punct p2)
{ 
	return sqrt(pow((double)p1.x-p2.x,2.0) + pow((double)p1.y-p2.y,2.0));
}
double distmin(int st, int dr)
{
	if (dr - st <= 2)
	{
		if (dr==st+1)
			return dist(v[st], v[dr]);
		if (dr==st+2)
		{
			double mini = dist(v[st],v[st+1]);
			double d2 = dist(v[dr],v[st+1]);
			double d3 = dist(v[st],v[dr]);
			if (mini > d2)
				mini = d2;
			if (mini > d3)
				mini = d3;
			return mini;
		}
	}
	else
	{
		int j,i,ls,ld;
		int mj = (st+dr)/2;
		double d = distmin(st,mj);
		double d2 = distmin(mj+1,dr);
		if (d > d2)
			d = d2;
		for (i=mj;i>=0;i--)
			if (v[mj].x - v[i].x > d)
				break;
		ls = i+1;
		for (i=mj+1;i<n;i++)
			if (v[i].x - v[mj+1].x > d)
				break;
		ld = i-1;
		for (i=ls;i<=mj;i++)
			for (j=mj+1;j<=ld;j++)
			{
				double d1 = dist(v[i],v[j]);
				if ( d1 < d)
					d = d1;
			}
		return d;
	}
}
int main()
{
	int i;
	ifstream fin("cmap.in");
	fin>>n;
	for (i=0;i<n;i++)
		fin >> v[i].x>>v[i].y;
	sort(v,v+n,cmp);
	cout<<fixed<<setprecision(6);
	cout<<distmin(0,n-1);
	ofstream fout("cmap.out");
	fout<<fixed<<setprecision(6);
	fout<<distmin(0,n-1);
	return 0;
}