Cod sursa(job #933166)

Utilizator raulstoinStoin Raul raulstoin Data 29 martie 2013 17:40:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector < pair<LL,LL> > X,Y,V(100005);
LL n;
LL oo=(1LL<<62);
void Read()
{
	LL x,y;
	fin>>n;
	for(LL i=0;i<n;i++)
	{
		fin>>x>>y;
		X.push_back(make_pair(x,y));
	}
	sort(X.begin(),X.end());
	for(LL i=0;i<n;i++)
		Y.push_back(make_pair(X[i].second,X[i].first));

}
LL dist(pair<LL,LL> A,pair<LL,LL> B)
{
	return (B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}

LL Solve(LL s,LL d, vector < pair <LL, LL> >& X, vector < pair <LL, LL> >& Y)
{
	if (s>=d-1)
		return oo;
	if(s+2==d)
	{
		if(Y[s]>Y[s+1])
			swap(Y[s],Y[s+1]);
		return dist(Y[s],Y[s+1]);
	}
	LL m=(s+d)/2;
	LL best=min(Solve(s,m,X,Y),Solve(m,d,X,Y));
	merge(Y.begin() + s, Y.begin() + m, Y.begin() + m, Y.begin() + d, V.begin());
	copy(V.begin(), V.begin() + (d - s), Y.begin() + s);
	LL SIZE=0;
	for(LL i=s;i<d;i++)
		if(abs(Y[i].second-X[m].first)<=best)
			V[SIZE++]=Y[i];
	for(size_t i=0;i<SIZE-1;i++)
		for(size_t j=i+1;j<SIZE&&j-i<8;j++)
			best=min(best,dist(V[i],V[j]));
	return best;
}
int main()
{
	Read();
	fout.precision(7);
	fout<<fixed<<sqrt(Solve(0,X.size(),X,Y));
	return 0;
}