Cod sursa(job #980639)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 5 august 2013 12:27:42
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb

#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>

typedef std::pair<int,int> Point;

const int MAX_N(100001);
const double MAX_VALUE(1 << 30);

int n;
Point v [MAX_N];

double Result(MAX_VALUE);

inline void Read (void)
{
	std::freopen("cmap.in","r",stdin);
	std::scanf("%d\n",&n);
	for (int i(1) ; i <= n ; ++i)
		std::scanf("%d %d\n",&v[i].first,&v[i].second);
	std::fclose(stdin);
}

inline void Print (void)
{
	std::freopen("cmap.out","w",stdout);
	std::printf("%.6lf",Result);
	std::fclose(stdout);
}

inline double EuclidianDistance (Point a, Point b)
{
	return std::sqrt(static_cast<unsigned long long>(std::abs(a.first - b.first)) * static_cast<unsigned long long>(std::abs(a.first - b.first)) + static_cast<unsigned long long>(std::abs(a.second - b.second)) * static_cast<unsigned long long>(std::abs(a.second - b.second)));
}

double Compute (int left, int right)
{
	if (left >= right)
		return MAX_VALUE;
	if (left == right - 1)
		return EuclidianDistance(v[left],v[right]);
	int mid((left + right) >> 1);
	double min(std::min(Compute(left,mid),Compute(mid + 1,right)));
	std::vector<Point> r;
	int i;
	for (i = left ; i <= right ; ++i)
		if (i != mid)
			if (std::abs(v[mid].first - v[i].first) < min)
				r.push_back(v[i]);
	int j, end;
	std::sort(r.begin(),r.end(), [ ] (Point a, Point b) {return a.second < b.second;});
	for (i = 0 ; i < r.size() ; ++i)
		for (j = i + 1 ; j <= i + 8 && j < r.size() ; ++j)
			min = std::min(min,EuclidianDistance(r[i],r[j]));
	return min;
}

int main (void)
{
	Read();
	std::sort(v + 1,v + n + 1);
	Result = Compute(1,n);
	Print();
	return 0;
}