Cod sursa(job #650719)

Utilizator ELHoriaHoria Cretescu ELHoria Data 18 decembrie 2011 20:29:17
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#define PDD pair<double,double>
#define MP make_pair
#define st first
#define nd second

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const double INF = 2e9;
int N;
vector < PDD > V(100005), X, Y;

double dist(const PDD &x,const PDD &y)
{
	return sqrt((x.st - y.st) * (x.st - y.st) + (x.nd - y.nd) * (x.nd - y.nd));
}

double solve(int st,int dr)
{
	if(dr - st == 1) 
		return INF;
	else if(dr - st == 2)
		{
			if(Y[st] > Y[st + 1]) 
				swap(Y[st],Y[st + 1]);
			return dist(X[st],X[st + 1]);
		}
	int mid = (st + dr)/2 , v_sz = 0;
	double bst = min(solve(st,mid),solve(mid,dr));
	merge(Y.begin() + st, Y.begin() + mid, Y.begin() + mid, Y.begin() + dr, V.begin());
	copy(V.begin(), V.begin() + (dr - st), Y.begin() + st);

	for(int i = st;i<dr;++i)
		if(abs(Y[i].nd - X[mid].st)<=bst) V[v_sz++] = Y[i];

	for(int i = 0;i<v_sz;++i)
		for(int j = i + 1;j<v_sz && j - i <8;++j)
			bst = min(bst,dist(V[i],V[j]));
	return bst;
}

int main()
{
	fin>>N;
	X.resize(N) , Y.resize(N);
	for(int i = 0;i<N;++i)
		fin>>X[i].st>>X[i].nd;

	sort(X.begin(),X.end());
	for(int i = 0;i<N;++i)
		Y[i] = MP(X[i].nd,X[i].st);

	fout<<fixed<<setprecision(6)<<solve(0,X.size());
	return 0;
}