Cod sursa(job #1617725)

Utilizator RobertSSamoilescu Robert RobertS Data 27 februarie 2016 16:01:36
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
 
struct Point{
    int x, y;
};
 
#define INF 0x7fffffff
 
int compare(const void *a, const void *b){
    Point *p1 = (Point*) a;
    Point *p2 = (Point*) b;
 
    if(p1->x > p2->x) return 1;
    else if(p1->x == p2->x){
        if(p1->y > p2->y) return 1;
        else if(p1->y == p2->y) return 0;
        else return 0;
    }else return -1;
     
}

 
 
double dist(const Point& p1, const Point& p2){
    return sqrt(pow((double)(p1.x - p2.x), 2) + pow((double)(p1.y - p2.y), 2));
}
 


 
double split_plane(Point *v, int li, int ls){
     
    if(ls - li<=2){
        double dmin1 = std::min(dist(v[li], v[li+1]), dist(v[li+1], v[li+2]));
        return std::min(dmin1, dist(v[li], v[li+2]));
    }else{
        int lm = (li + ls) / 2; 
        int xm = v[lm].x; /*dreapta care imparte planul*/
 
        double dmin = std::min(split_plane(v, li, lm), split_plane(v, lm+1, ls));
         
        std::vector<Point> region; /*vector de puncte delimitat de distana d*/
        for(int i = lm; i >=0 && abs(xm - v[i].x) < dmin; i--)
	  for(int j = 1; j <= 6 && (i+j <= ls); j++)
		dmin = std::min(dmin, dist(v[i], v[i+j]));
         
	     
       
        return dmin;
    }
 
 
     
 
}
 
int main(){
     
    std::ifstream fin("cmap.in");
    std::ofstream fout("cmap.out");
 
    int n;
    fin >> n;
     
     
    Point v[n+1];
 
    for(int i = 0; i < n; i++){
        fin >> v[i].x >> v[i].y;
    }
     
    qsort(v, n, sizeof(Point), compare);
     
 
    double dmin = split_plane(v, 0, n-1);
    fout.precision(8);
    fout << dmin << '\n';
 
    fin.close();
    fout.close();
    return 0;   
}