Cod sursa(job #1163068)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 1 aprilie 2014 09:54:38
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
//dupa ideea O(nlogn) si codul lui Marius Stroe
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>

typedef long long int LL;
typedef std::pair<LL,LL> PLL;

const LL INF=std::numeric_limits<LL>::max();

LL dist(PLL a, PLL b){ return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second); }

std::vector<PLL> X,Y,temp;

LL get(unsigned st, unsigned dr){
	if(st+1>=dr) return INF;

	else if(dr-st==2){
		if(Y[st]>Y[st+1]) Y[st].swap(Y[st+1]);
		return dist(X[st],X[st+1]);
	}

	else{
		unsigned mid=(st+dr)>>1;
		LL best = std::min( get(st,mid), get(mid,dr) );

        std::merge(Y.begin()+st, Y.begin()+mid, Y.begin()+mid, Y.begin()+dr, temp.begin());
		std::copy(temp.begin(), temp.begin()+(dr-st), Y.begin()+st);

		unsigned tsz=0;

		for(unsigned i=st;i<dr;++i)
			if(std::abs(Y[i].second-X[mid].first)<=best)
				temp[tsz++]=Y[i];

		for(unsigned i=0;i<tsz-1;++i)
			for(unsigned j=i+1;j<tsz && j-i<8;++j)
				best = std::min(best, dist(temp[i],temp[j]));

		return best;
	}
}


int main(){
	std::freopen("cmap.in","r",stdin);
	std::freopen("cmap.out","w",stdout);

	unsigned n; std::scanf("%u",&n);
	X.resize(n); Y.resize(n); temp.resize(n);

	for(unsigned i=0;i<n;++i) std::scanf("%lld %lld",&X[i].first,&X[i].second);

	std::sort(X.begin(),X.end());

	for(unsigned i=0;i<n;++i){ Y[i].first=X[i].second; Y[i].second=X[i].first; }

	std::printf("%.8Lf\n",std::sqrt(static_cast<long double>(get(0,n))));
}