Cod sursa(job #980660)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 5 august 2013 13:23:38
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 10.2 kb

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

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

const int DIM(2);
const int MAX_VALUE(1 << 30);
const double GUARD(0.000001);

inline double Area (Polygon &v)
{
    const int END(v.size());
    v.push_back(v.front());
    long long result(0);
    for (int i(0) ; i < END ; ++i)
        result += static_cast<long long>(v[i].first) * v[i + 1].second - static_cast<long long>(v[i].second) * v[i + 1].first;
    v.pop_back();
    return static_cast<double>(std::abs(result)) / 2;
}

inline bool InPolygon (Polygon &v, Point p)
{
	const int END(v.size() - 1);
	Polygon temp(3);
	temp[0] = p;
	const double AREA(Area(v));
	double area(0);
	for (int index(0) ; index < END ; ++index)
	{
		temp[1] = v[index];
		temp[2] = v[index + 1];
		area += Area(temp);
	}
	temp[1] = v[0];
	temp[2] = v[END];
	area += Area(temp);
	return area >= AREA - GUARD && area <= AREA - GUARD;
}

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)));
}

inline int PerpendicularDistance (Point a, Point b, int dimension)
{
	return std::abs((dimension ? a.second - b.second : a.first - b.first));
}

struct KDTree
{
	Point p;
	struct KDTree *left = nullptr;
	struct KDTree *right = nullptr;
	struct KDTree *parent = nullptr;
	int cd;
} *Root;

inline void Initialise (struct KDTree *&node)
{
	node = new struct KDTree ( );
}

void Build (std::vector<Point> &v, struct KDTree *&node, struct KDTree *parent, int dimension, int left, int right)
{
	if (left > right)
		return;
	if (dimension == 0)
		std::nth_element(v.begin() + left,v.begin() + left + ((right - left) >> 1),v.begin() + right + 1,[ ] (Point a, Point b) {return a.first < b.first;});
	else
		std::nth_element(v.begin() + left,v.begin() + left + ((right - left) >> 1),v.begin() + right + 1,[ ] (Point a, Point b) {return a.second < b.second;});
	Initialise(node);
	node->p = v[left + ((right - left) >> 1)];
	node->parent = parent;
	node->cd = dimension;
	Build(v,node->left,node,(dimension + 1) % DIM,left,left + ((right - left) >> 1) - 1);
	Build(v,node->right,node,(dimension + 1) % DIM,left + ((right - left) >> 1) + 1,right);
}

inline void Insert (struct KDTree *&root, Point p)
{
	int dimension(0);
	struct KDTree *iterator(root), *parent(nullptr);
	bool turn(0);
	while (true)
	{
		if (!iterator)
		{
			if (!root)
			{
				Initialise(root);
				iterator = root;
			}
			else
				Initialise(iterator);
			iterator->p = p;
			iterator->parent = parent;
			iterator->cd = dimension;
			if (parent)
			{
				if (turn)
					parent->right = iterator;
				else
					parent->left = iterator;
			}
			break;
		}
		if (iterator->p == p)
		{
			// Duplicate
			break;
		}
		parent = iterator;
		if (dimension == 0)
		{
			if (p.first > iterator->p.first)
			{
				turn = true;
				iterator = iterator->right;
			}
			else
			{
				turn = false;
				iterator = iterator->left;
			}
		}
		else
		{
			if (p.second > iterator->p.second)
			{
				turn = true;
				iterator = iterator->right;
			}
			else
			{
				turn = false;
				iterator = iterator->left;
			}
		}
		dimension = (dimension + 1) % DIM;
	}
}

struct KDTree *Search (struct KDTree *root, Point p)
{
	struct KDTree *node(root);
	while (true)
	{
		if (!node)
			return nullptr;
		if (node->p == p)
			return node;
		if (node->cd == 0)
		{
			if (p.first > node->p.first)
				node = node->right;
			else if (p.first < node->p.first)
				node = node->left;
			else
			{
				struct KDTree *candidate(Search(node->left,p));
				if (candidate)
					return candidate;
				return Search(node->right,p);
			}
		}
		else
		{
			if (p.second > node->p.second)
				node = node->right;
			else if (p.second < node->p.second)
				node = node->left;
			else
			{
				struct KDTree *candidate(Search(node->left,p));
				if (candidate)
					return candidate;
				return Search(node->right,p);
			}
		}
	}
}

struct KDTree *FindMin (struct KDTree *node, int cd)
{
	if (!node)
		return nullptr;
	if (node->cd == cd)
	{
		if (node->left)
			return FindMin(node->left,cd);
		return node;
	}
	struct KDTree *result(node), *candidate(FindMin(node->left,cd)), *temp(FindMin(node->right,cd));
	if (!candidate)
		candidate = temp;
	if (candidate && temp)
	{
		if (cd == 0)
			candidate = (candidate->p.first < temp->p.first ? candidate : temp);
		else
			candidate = (candidate->p.second < temp->p.second ? candidate : temp);
	}
	if (candidate)
	{
		if (cd == 0)
			result = (result->p.first < candidate->p.first ? result : candidate);
		else
			result = (result->p.second < candidate->p.second ? result : candidate);
	}
	return result;
}

void Remove (struct KDTree *&root, struct KDTree *node)
{
	if (node->right)
	{
		struct KDTree *min(FindMin(node->right,node->cd));
		node->p = min->p;
		Remove(root,min);
	}
	else if (node->left)
	{
		struct KDTree *min(FindMin(node->left,node->cd));
		node->p = min->p;
		Remove(root,min);
		node->right = node->left;
		node->left = nullptr;
	}
	else
	{
		// node is a leaf
		if (node->parent)
		{
			// If not root
			if (node == node->parent->left)
				node->parent->left = nullptr;
			else
				node->parent->right = nullptr;
		}
		else
			root = nullptr;
		delete node;
	}
}

inline void Delete (struct KDTree *&root, Point p)
{
	struct KDTree *iterator(Search(root,p));
	if (iterator)
		Remove(root,iterator);
}

struct KDTree *NearestNeighbor (struct KDTree *node, Point p, double min)
{
	if (!node)
		return nullptr;
	double d(EuclidianDistance(node->p,p));
	struct KDTree *best(nullptr);
	if (d < min)
	{
		best = node;
		min = d;
	}
	int pd(PerpendicularDistance(p,node->p,node->cd));
	struct KDTree *candidate;
	if (pd < min)
	{
		candidate = NearestNeighbor(node->left,p,min);
		if (candidate)
		{
			d = EuclidianDistance(candidate->p,p);
			if (d < min)
			{
				best = candidate;
				min = d;
			}
		}
		candidate = NearestNeighbor(node->right,p,min);
		if (candidate)
			return candidate;
	}
	else
	{
		if (node->cd == 0)
		{
			if (p.first > node->p.first)
				candidate = NearestNeighbor(node->right,p,min);
			else
				candidate = NearestNeighbor(node->left,p,min);
		}
		else
		{
			if (p.second > node->p.second)
				candidate = NearestNeighbor(node->right,p,min);
			else
				candidate = NearestNeighbor(node->left,p,min);
		}
		if (candidate)
			return candidate;
	}
	return best;
}

struct KDTree *NearestNeighbor (struct KDTree *root, Point p)
{
	if (!root)
		return nullptr;
	// First of all find the parent node where p would have been inserted
	struct KDTree *node(root), *trace(root);
	while (node)
	{
		trace = node;
		if (node->cd == 0)
		{
			if (p.first > node->p.first)
				node = node->right;
			else
				node = node->left;
		}
		else
		{
			if (p.second > node->p.second)
				node = node->right;
			else
				node = node->left;
		}
	}
	double d(EuclidianDistance(trace->p,p));
	node = NearestNeighbor(root,p,d);
	if (node)
		return node;
	return trace;
}

void RangeSearch (struct KDTree *node, Polygon &v, int extreme [ ], Polygon &result)
{
	if (!node)
		return;
	if (node->cd == 0)
	{
		if (node->p.first >= extreme[0] && node->p.first <= extreme[1])
		{
			if (InPolygon(v,node->p))
				result.push_back(node->p);
			RangeSearch(node->left,v,extreme,result);
			RangeSearch(node->right,v,extreme,result);
		}
		else if (node->p.first < extreme[0])
			RangeSearch(node->right,v,extreme,result);
		else if (node->p.first > extreme[1])
			RangeSearch(node->left,v,extreme,result);
	}
	else
	{
		if (node->p.second >= extreme[2] && node->p.second <= extreme[3])
		{
			if (InPolygon(v,node->p))
				result.push_back(node->p);
			RangeSearch(node->left,v,extreme,result);
			RangeSearch(node->right,v,extreme,result);
		}
		else if (node->p.second < extreme[2])
			RangeSearch(node->right,v,extreme,result);
		else if (node->p.second > extreme[3])
			RangeSearch(node->left,v,extreme,result);
	}
}

inline std::vector<Point> RangeSearch (struct KDTree *root, Polygon &v)
{
	Polygon result;
	if (v.size() < 3)
		return result;
	int extreme [ ] = {MAX_VALUE, MAX_VALUE, -MAX_VALUE, -MAX_VALUE};
	for (auto it : v)
	{
		if (it.first < extreme[0])
			extreme[0] = it.first;
		if (it.first > extreme[1])
			extreme[1] = it.first;
		if (it.second < extreme[2])
			extreme[2] = it.second;
		if (it.second > extreme[3])
			extreme[3] = it.second;
	}
	RangeSearch(root,v,extreme,result);
	return result;
}

void RectangleRangeSearch (struct KDTree *node, Point left, Point right, Polygon &result)
{
	if (!node)
		return;
	if (node->cd == 0)
	{
		if (node->p.first >= left.first && node->p.first <= right.first)
		{
			if (node->p.second <= left.second && node->p.second >= right.second)
				result.push_back(node->p);
			RectangleRangeSearch(node->left,left,right,result);
			RectangleRangeSearch(node->right,left,right,result);
		}
		else if (node->p.first < left.first)
			RectangleRangeSearch(node->right,left,right,result);
		else if (node->p.first > right.first)
			RectangleRangeSearch(node->left,left,right,result);
	}
	else
	{
		if (node->p.second <= left.second && node->p.second >= right.second)
		{
			if (node->p.first >= left.first && node->p.first <= right.first)
				result.push_back(node->p);
			RectangleRangeSearch(node->left,left,right,result);
			RectangleRangeSearch(node->right,left,right,result);
		}
		else if (node->p.second > left.second)
			RectangleRangeSearch(node->left,left,right,result);
		else if (node->p.second < right.second)
			RectangleRangeSearch(node->right,left,right,result);
	}
}

inline std::vector<Point> RectangleRangeSearch (struct KDTree *root, Point left, Point right)
{
	Polygon result;
	RectangleRangeSearch(root,left,right,result);
	return result;
}

int main (void)
{
	std::freopen("cmap.in","r",stdin);
	std::freopen("cmap.out","w",stdout);
	int n;
	struct KDTree *root(nullptr), *result;
	double min(1 << 30);
	std::scanf("%d",&n);
	for (int i(1), a, b ; i <= n ; ++i)
	{
		std::scanf("%d %d\n",&a,&b);
		result = NearestNeighbor(root,std::make_pair(a,b));
		if (result)
			min = std::min(min,EuclidianDistance(result->p,std::make_pair(a,b)));
		Insert(root,std::make_pair(a,b));
	}
	std::printf("%.6lf\n",min);
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}