Cod sursa(job #2226753)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 30 iulie 2018 16:17:38
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 5.37 kb
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstdio>

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:
	///1-indexed because 0 is reserved for NULL, has a heap-like structure
	///(x,y) of points are swaped depending on level
	int root;
	vector<point_data_t> point;
	vector<int> leftson;
	vector<int> rightson;

	public:
	KDTree(){
		root = 0;
	}
	
	KDTree(vector<point_data_t> &points){///constructs iteratively the tree
		root = (1 + (int)points.size()) / 2;
		point.push_back(point_data_t(0,0));
		for(auto &it:points){
			point.push_back(it);
		}
		
		leftson.resize(point.size());
		rightson.resize(point.size());
		
		queue< pair<int,int> > points_queue;///[left,right] of interval.1-indexed
		points_queue.push({1,points.size()});
		
		while(!points_queue.empty()){
			int left = points_queue.front().first;
			int right = points_queue.front().second;
			points_queue.pop();
			int mid = (left + right) / 2;
			nth_element(point.begin() + left,point.begin() + mid,point.begin() + right + 1);
			
			if(left < mid){
				points_queue.push({left,mid - 1});
				for(int i = left;i < mid;i++){
					swap(point[i].x,point[i].y);
				}
				leftson[mid] = (left + mid - 1) / 2;
			}
			
			if(mid < right){
				points_queue.push({mid + 1,right});
				for(int i = mid + 1;i <= right;i++){
					swap(point[i].x,point[i].y);
				}
				rightson[mid] = (mid + right + 1) / 2;
			}
		}
	}
	
	point_data_t find_nearest_neighbour(point_data_t &P,double &best_dist_so_far,int root = -1){
		root = (root == -1 ? this->root:root);
		point_data_t best_point_in_subtree = point[root];
		
		if(P != point[root] && best_dist_so_far > (P - point[root]).sqr_len()){
			best_dist_so_far = (P - point[root]).sqr_len();
		}
		
		if(leftson[root] == 0 && rightson[root] == 0){
			return best_point_in_subtree;
		}
		
		if(leftson[root] == 0){
			swap(P.x,P.y);
			point_data_t rightson_answer = find_nearest_neighbour(P,best_dist_so_far,rightson[root]);
			swap(P.x,P.y);
			swap(rightson_answer.x,rightson_answer.y);
			
			if((P - best_point_in_subtree).sqr_len() > (P - rightson_answer).sqr_len()){
				best_point_in_subtree = rightson_answer;
			}
			
			return best_point_in_subtree;
		}
		
		if(rightson[root] == 0){
			swap(P.x,P.y);
			point_data_t leftson_answer = find_nearest_neighbour(P,best_dist_so_far,leftson[root]);
			swap(P.x,P.y);
			swap(leftson_answer.x,leftson_answer.y);
			
			if((P - best_point_in_subtree).sqr_len() > (P - leftson_answer).sqr_len()){
				best_point_in_subtree = leftson_answer;
			}
			
			return best_point_in_subtree;
		}
		
		if(P < point[root]){
			swap(P.x,P.y);
			point_data_t leftson_answer = find_nearest_neighbour(P,best_dist_so_far,leftson[root]);
			swap(P.x,P.y);
			swap(leftson_answer.x,leftson_answer.y);
			
			if((P - best_point_in_subtree).sqr_len() > (P - leftson_answer).sqr_len()){
				best_point_in_subtree = leftson_answer;
			}
			
			if(P.x + sqrt(best_dist_so_far) >= point[root].x){
				swap(P.x,P.y);
				point_data_t leftson_answer = find_nearest_neighbour(P,best_dist_so_far,leftson[root]);
				swap(P.x,P.y);
				swap(leftson_answer.x,leftson_answer.y);
				
				if((P - best_point_in_subtree).sqr_len() > (P - leftson_answer).sqr_len()){
					best_point_in_subtree = leftson_answer;
				}
			}
			return best_point_in_subtree;
		}
		
		else{
			swap(P.x,P.y);
			point_data_t rightson_answer = find_nearest_neighbour(P,best_dist_so_far,rightson[root]);
			swap(P.x,P.y);
			swap(rightson_answer.x,rightson_answer.y);
			
			if((P - best_point_in_subtree).sqr_len() > (P - rightson_answer).sqr_len()){
				best_point_in_subtree = rightson_answer;
			}
			
			if(P.x - sqrt(best_dist_so_far) <= point[root].x){
				swap(P.x,P.y);
				point_data_t leftson_answer = find_nearest_neighbour(P,best_dist_so_far,leftson[root]);
				swap(P.x,P.y);
				swap(leftson_answer.x,leftson_answer.y);
				
				if((P - best_point_in_subtree).sqr_len() > (P - leftson_answer).sqr_len()){
					best_point_in_subtree = leftson_answer;
				}
			}
			return best_point_in_subtree;
		}
	}
	
	void print_tree(){
		printf("%d\n",root);
		for(int i = 1;i < (int)point.size();i++){
			printf("%d %d %d %.5f %.5f\n",i,leftson[i],rightson[i],point[i].x,point[i].y);
		}
	}
};

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

int main(){
	
	fscanf(f,"%d",&N);
	V.resize(N);
	
	for(int i = 0;i < N;i++){
		fscanf(f,"%lf %lf",&V[i].x,&V[i].y);
	}
	
	KDTree T(V);
	
	double ans = 5e18;
	
	for(auto &it:V){
		T.find_nearest_neighbour(it,ans);
	}
	
	fprintf(g,"%.6f",sqrt(ans));
	
	fclose(f);
	fclose(g);
	
	return 0;
}