#include <cstdio>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <typeinfo>

// using namespace std;

struct point_data_t{
	double x,y;
	
	point_data_t(){
		x = y = 0;
	}
	
	point_data_t(double x,double y){
		this->x = x;
		this->y = y;
	}
	
	double sqr_len(){
		return x * x + y * y; 
	}
	
	double len(){
		return sqrt(sqr_len());
	}
	
	point_data_t operator - (point_data_t &other)const{
		return point_data_t(x - other.x,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;
	}
};


class KDTree{
private:
	KDTree *leftson,*rightson;
	point_data_t P;
public:
	
	KDTree(){
		leftson = rightson = NULL;
		P = point_data_t(0,0);
	}
	
	~KDTree(){
		if(leftson != NULL){
			delete leftson;
		}
		
		if(rightson != NULL){
			delete rightson;
		}
	}
	
	KDTree(KDTree *leftson,KDTree *rightson,point_data_t P){
		this->leftson = leftson;
		this->rightson = rightson;
		this->P = P;
	}
	
	void build(std::vector<point_data_t> &points,int left,int right){///[left,right);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);
		}
	}
	
		///best_dist_so_far contains the actual distance squared;leaves P uneffected,returns the closeste point
	point_data_t find_nearest_neighbour(point_data_t &P,double &best_dist_so_far){///P has the coordonates in order for this depth,returns the answer with coordinates swaped depending on the depth
		
		point_data_t best_subtree_point = this->P;
		
		if(best_dist_so_far > (this->P - P).sqr_len()){
			best_dist_so_far = (this->P - P).sqr_len();
			best_subtree_point = this->P;
		}
		
		if(leftson == NULL && rightson == NULL){
			return best_subtree_point;
		}
		
		if(leftson == NULL){
			
			std::swap(P.x,P.y);
			point_data_t rightson_ans = this->rightson->find_nearest_neighbour(P,best_dist_so_far);
			std::swap(P.x,P.y);
			std::swap(rightson_ans.x,rightson_ans.y);
			
			if((P - best_subtree_point).sqr_len() > (P - rightson_ans).sqr_len()){
				best_subtree_point = rightson_ans;
			}
			return best_subtree_point;
		}
		
		if(rightson == NULL){
			std::swap(P.x,P.y);
			point_data_t leftson_ans = this->leftson->find_nearest_neighbour(P,best_dist_so_far);
			std::swap(P.x,P.y);
			std::swap(leftson_ans.x,leftson_ans.y);
			
			if((P - best_subtree_point).sqr_len() > (P - leftson_ans).sqr_len()){
				best_subtree_point = leftson_ans;
			}
			return best_subtree_point;
		}			
		
		if(P < this->P){
			std::swap(P.x,P.y);
			point_data_t leftson_ans = this->leftson->find_nearest_neighbour(P,best_dist_so_far);
			std::swap(P.x,P.y);
			std::swap(leftson_ans.x,leftson_ans.y);
			
			if((P - best_subtree_point).sqr_len() > (P - leftson_ans).sqr_len()){
				best_subtree_point = leftson_ans;
			}
			
			if(P.x + sqrt(best_dist_so_far) >= this->P.x){
				std::swap(P.x,P.y);
				point_data_t rightson_ans = this->rightson->find_nearest_neighbour(P,best_dist_so_far);
				std::swap(P.x,P.y);
				std::swap(rightson_ans.x,rightson_ans.y);
				
				if((P - best_subtree_point).sqr_len() > (P - rightson_ans).sqr_len()){
					best_subtree_point = rightson_ans;
				}
			}
			return best_subtree_point;
		}
		else{
			std::swap(P.x,P.y);
			point_data_t rightson_ans = this->rightson->find_nearest_neighbour(P,best_dist_so_far);
			std::swap(P.x,P.y);
			std::swap(rightson_ans.x,rightson_ans.y);
			
			if((P - best_subtree_point).sqr_len() > (P - rightson_ans).sqr_len()){
				best_subtree_point = rightson_ans;
			}
			
			if(P.x - sqrt(best_dist_so_far) <= this->P.x){
				std::swap(P.x,P.y);
				point_data_t leftson_ans = this->leftson->find_nearest_neighbour(P,best_dist_so_far);
				std::swap(P.x,P.y);
				std::swap(leftson_ans.x,leftson_ans.y);
				
				if((P - best_subtree_point).sqr_len() > (P - leftson_ans).sqr_len()){
					best_subtree_point = leftson_ans;
				}
			}
			return best_subtree_point;
		}
	}
	
	KDTree(std::vector<point_data_t> points){
		this->build(points,0,(int)points.size());
	}
	
	void print_tree(){
		// cout << this << " " << leftson << " " << rightson << " " << P.x << " " << P.y << "\n";
		
		if(leftson != NULL){
			this->leftson->print_tree();
		}
		
		if(rightson != NULL){
			this->rightson->print_tree();
		}
	}
};

std::vector<point_data_t> first_input_points = {
	point_data_t(-24,15),
	point_data_t(-13,15),
	point_data_t(-11,10),
	point_data_t(-21,5),
	point_data_t(-13,2),
	point_data_t(-4,4),
	point_data_t(5,5),
	point_data_t(13,12),
	point_data_t(21,8),
	point_data_t(23,1),
	point_data_t(-20,-9),
	point_data_t(-9,-8),
	point_data_t(4,-4),
	point_data_t(16,-11)
};

std::vector<point_data_t> first_input_querys = {
	point_data_t(-18,11),
	point_data_t(6,11),
	point_data_t(10,10),
	point_data_t(21,11),
	point_data_t(-5,2),
	point_data_t(2,2),
	point_data_t(16,1),
	point_data_t(0,0),
	point_data_t(10,0),
	point_data_t(25,-4),
	point_data_t(-11,-11),
	point_data_t(16,-16)
};

std::vector<point_data_t> first_input_answers = {
	point_data_t(-13,15),
	point_data_t(5,5),
	point_data_t(13,12),
	point_data_t(21,8),
	point_data_t(-4,4),
	point_data_t(5,5),
	point_data_t(23,1),
	point_data_t(-4,4),
	point_data_t(5,5),
	point_data_t(23,1),
	point_data_t(-9,-8),
	point_data_t(16,-11)
};
std::vector<point_data_t> second_input_points = {
	point_data_t(2,4),
	point_data_t(0.5,2),
	point_data_t(3.5,6),
	point_data_t(7,0),
	point_data_t(1,2.3),
	point_data_t(2.5,6.2)
};

std::vector<point_data_t> second_input_querys = {
	point_data_t(1,2.3),
	point_data_t(4,2.3),
	point_data_t(5,1.7),
	point_data_t(6.4,5.2),
	point_data_t(6.9,9.6)
};

std::vector<point_data_t> second_input_answers = {
	
};

void run_test(std::vector<point_data_t> &points,std::vector<point_data_t> &querys){
	
	
	std::ofstream g("out");
	KDTree *root;
	
	root = new KDTree(points);
	
	for(auto query:querys){
		double ans = 5e18;
		auto tmp = root->find_nearest_neighbour(query,ans);
		g << tmp.x << " " << tmp.y << "\n";
	}
	
	delete root;
	
	std::ofstream h("ok");
	for(auto it:querys){
		double mindist = 5e18;
		point_data_t ans;
		for(auto it2:points){
			if(mindist > (it - it2).sqr_len()){
				mindist = (it - it2).sqr_len();
				ans = it2;
			}
		}
		h << ans.x << " " << ans.y << "\n";
	}
}

using namespace std;

int main(){
	
	///run_test(second_input_points,second_input_querys);
	KDTree *root = new KDTree;
	cout << typeid(root).name();
	return 0;
}