Cod sursa(job #2228000)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 2 august 2018 13:58:41
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 6.26 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cassert>
     
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(const 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;
    }
};
    
    
class KDTree{
private:
    KDTree *leftson,*rightson;
    point_data_t<int> P;
public:
        
    KDTree(){
        leftson = rightson = NULL;
        P = point_data_t<int>(0,0);
    }
        
    ~KDTree(){
        if(leftson != NULL){
            delete leftson;
        }
            
        if(rightson != NULL){
            delete rightson;
        }
    }
        
    KDTree(KDTree *leftson,KDTree *rightson,point_data_t<int> P){
        this->leftson = leftson;
        this->rightson = rightson;
        this->P = P;
    }
        
    void build(vector<point_data_t<int>> &points,int left,int right);
        
        ///best_dist_so_far contains the actual distance squared;leaves P uneffected,returns the closeste point
    point_data_t<int> find_nearest_neighbour(point_data_t<int> &P,double &best_dist_so_far);
        
    KDTree(vector<point_data_t<int>> points);
};
    
void KDTree::build(vector<point_data_t<int>> &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++){
        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++){
        swap(points[i].x,points[i].y);
    }
}
  
point_data_t<int> KDTree::find_nearest_neighbour(point_data_t<int> &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<int> 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){
            
        swap(P.x,P.y);
        point_data_t<int> rightson_ans = this->rightson->find_nearest_neighbour(P,best_dist_so_far);
        swap(P.x,P.y);
        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){
        swap(P.x,P.y);
        point_data_t<int> leftson_ans = this->leftson->find_nearest_neighbour(P,best_dist_so_far);
        swap(P.x,P.y);
        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){
        swap(P.x,P.y);
        point_data_t<int> leftson_ans = this->leftson->find_nearest_neighbour(P,best_dist_so_far);
        swap(P.x,P.y);
        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){
            swap(P.x,P.y);
            point_data_t<int> rightson_ans = this->rightson->find_nearest_neighbour(P,best_dist_so_far);
            swap(P.x,P.y);
            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{
        swap(P.x,P.y);
        point_data_t<int> rightson_ans = this->rightson->find_nearest_neighbour(P,best_dist_so_far);
        swap(P.x,P.y);
        swap(rightson_ans.x,rightson_ans.y);
            
        if(P.dist(best_subtree_point) > P.dist(best_subtree_point)){
            best_subtree_point = rightson_ans;
        }
            
        if(P.x - best_dist_so_far <= this->P.x){
            swap(P.x,P.y);
            point_data_t<int> leftson_ans = this->leftson->find_nearest_neighbour(P,best_dist_so_far);
            swap(P.x,P.y);
            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;
    }
}
  
KDTree::KDTree(vector<point_data_t<int>> points){
    this->build(points,0,(int)points.size());
}
    
int N;
vector<point_data_t<int>> V;
FILE *f = fopen("cmap.in","r");
FILE *g = fopen("cmap.out","w");
     
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 *root = new KDTree(V);
    double ans = 5e18;
      
    for(auto it:V){
        double tmp = 5e18;
        root->find_nearest_neighbour(it,tmp);
        ans = min(tmp,ans);
    }
         
    fprintf(g,"%.7f",ans);
         
    fclose(f);
    fclose(g);
         
    return 0;
}