Cod sursa(job #2227940)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 2 august 2018 11:40:31
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 5.45 kb
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstdio>

using namespace std;

template <typename coord_type>
struct point_data_t{
	coord_type x,y;

	point_data_t(){
		x = y = 0;
	}

	point_data_t(coord_type x,coord_type y){
		this->x = x;
		this->y = y;
	}

	double dist(point_data_t &other)const{
		return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
	}

	bool operator < (const point_data_t &other)const{
		if(x != other.x){
			return x < other.x;
		}
		return y < other.y;
	}

	bool operator == (const point_data_t &other)const{
		return x == other.x && y == other.y;
	}

	bool operator != (const point_data_t &other)const{
		return x != other.x || y != other.y;
	}
};

///point_type should be a data structure that supports all point_data_t methods and has two variables x and y which will be used as coordinates

template <typename point_type>
class KDTree{
private:
	KDTree *leftson,*rightson;
	point_type P;
public:

	KDTree(){
		leftson = rightson = NULL;
		P = point_type(0,0);
	}

	~KDTree(){
		if(leftson != NULL){
			delete leftson;
		}

		if(rightson != NULL){
			delete rightson;
		}
	}

	KDTree(KDTree *leftson,KDTree *rightson,point_type P){
		this->leftson = leftson;
		this->rightson = rightson;
		this->P = P;
	}

	KDTree(std::vector<point_type> &points);

	void build(std::vector<point_type> &points,int left,int right);

	point_type find_nearest_neighbor(point_type &P,double &best_dist_so_far);
};

template<typename point_type>
void KDTree<point_type>::build(std::vector<point_type> &points,int left,int right){///[left,right);std::swaps x and y of points to prevent two compare functions;changes the order of parameter points
	int mid = (left + right) / 2;
	nth_element(points.begin() + left,points.begin() + mid,points.begin() + right);

	this->P = points[mid];

	for(int i = left;i < right;i++){
		std::swap(points[i].x,points[i].y);
	}

	if(left < mid){
		this->leftson = new KDTree;
		this->leftson->build(points,left,mid);
	}

	if(mid + 1 < right){
		this->rightson = new KDTree;
		this->rightson->build(points,mid + 1,right);
	}

	for(int i = left;i < right;i++){
		std::swap(points[i].x,points[i].y);
	}
}

template<typename point_type>
KDTree<point_type>::KDTree(std::vector<point_type> &points) {
	this->build(points,0,(int)points.size());
}

///best_dist_so_far contains the actual distance;leaves P uneffected,returns the closeste point
template<typename point_type>
point_type KDTree<point_type>::find_nearest_neighbor(point_type &P,double &best_dist_so_far){///P has the coordonates in order for this depth,returns the answer with coordinates std::swaped depending on the depth

	point_type best_subtree_point = this->P;

	if(P != this->P && best_dist_so_far > P.dist(this->P)){
		best_dist_so_far = P.dist(this->P);
		best_subtree_point = this->P;
	}

	if(leftson == NULL && rightson == NULL){
		return best_subtree_point;
	}

	if(leftson == NULL){

		std::swap(P.x,P.y);
		point_type rightson_ans = this->rightson->find_nearest_neighbor(P,best_dist_so_far);
		std::swap(P.x,P.y);
		std::swap(rightson_ans.x,rightson_ans.y);

		if(P.dist(best_subtree_point) > P.dist(rightson_ans)){
			best_subtree_point = rightson_ans;
		}
		return best_subtree_point;
	}

	if(rightson == NULL){
		std::swap(P.x,P.y);
		point_type leftson_ans = this->leftson->find_nearest_neighbor(P,best_dist_so_far);
		std::swap(P.x,P.y);
		std::swap(leftson_ans.x,leftson_ans.y);

		if(P.dist(best_subtree_point) > P.dist(leftson_ans)){
			best_subtree_point = leftson_ans;
		}
		return best_subtree_point;
	}

	if(P < this->P){
		std::swap(P.x,P.y);
		point_type leftson_ans = this->leftson->find_nearest_neighbor(P,best_dist_so_far);
		std::swap(P.x,P.y);
		std::swap(leftson_ans.x,leftson_ans.y);

		if(P.dist(best_subtree_point) > P.dist(leftson_ans)){
			best_subtree_point = leftson_ans;
		}

		if(P.x + best_dist_so_far >= this->P.x){
			std::swap(P.x,P.y);
			point_type rightson_ans = this->rightson->find_nearest_neighbor(P,best_dist_so_far);
			std::swap(P.x,P.y);
			std::swap(rightson_ans.x,rightson_ans.y);

			if(P.dist(best_subtree_point) > P.dist(rightson_ans)){
				best_subtree_point = rightson_ans;
			}
		}
		return best_subtree_point;
	}
	else{
		std::swap(P.x,P.y);
		point_type rightson_ans = this->rightson->find_nearest_neighbor(P,best_dist_so_far);
		std::swap(P.x,P.y);
		std::swap(rightson_ans.x,rightson_ans.y);

		if(P.dist(best_subtree_point) > P.dist(rightson_ans)){
			best_subtree_point = rightson_ans;
		}

		if(P.x - best_dist_so_far <= this->P.x){
			std::swap(P.x,P.y);
			point_type leftson_ans = this->leftson->find_nearest_neighbor(P,best_dist_so_far);
			std::swap(P.x,P.y);
			std::swap(leftson_ans.x,leftson_ans.y);

			if(P.dist(best_subtree_point) > P.dist(leftson_ans)){
						best_subtree_point = leftson_ans;
			}
		}
		return best_subtree_point;
	}
}



FILE *f = fopen("cmap.in","r");
FILE *g = fopen("cmap.out","w");
int N;
vector<point_data_t<int> > V;

int main(){
	
	fscanf(f,"%d",&N);
	V.resize(N);
	
	for(int i = 0;i < N;i++){
		fscanf(f,"%d %d",&V[i].x,&V[i].y);
	}
	
	KDTree<point_data_t<int> > *T = new KDTree<point_data_t<int> > (V);
	
	double ans = 5e18;
	
	for(auto &it:V){
		double tmp = 1e18;
		T->find_nearest_neighbor(it,tmp);
		ans = min(ans,tmp);
	}
	
	fprintf(g,"%.6f",ans);
	
	fclose(f);
	fclose(g);
	
	return 0;
}