Cod sursa(job #1618117)

Utilizator RobertSSamoilescu Robert RobertS Data 27 februarie 2016 18:20:05
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include<iomanip>
struct Point{
    int x, y;
};
 
#define INF 0x7fffffff

bool cmp_x(Point p1, Point p2){
	return p1.x < p2.x;
}

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


std::vector<Point>slice(std::vector<Point> v, int start, int end){
	std::vector<Point> a;
	a.assign(v.begin() + start, v.begin() + end);
	return a;
}
 
double brute_force(std::vector<Point> v){
	double dmin = INF;
	for(size_t i = 0; i < v.size() - 1; i++)
		for(size_t j = i+1; j < v.size(); j++)
			dmin = std::min(dmin, dist(v[i], v[j]));
		
	
	
	return dmin;
}

 
double split_plane(std::vector<Point>v){
     
	if(v.size()<=3){
		return brute_force(v);
	}else{
		int lm = v.size() / 2; 
		int xm = v[lm].x; /*dreapta care imparte planul*/
		 
		double dmin = std::min(split_plane(slice(v, 0, lm+1)), split_plane(slice(v, lm+1, v.size())));
		         
		
		int li, ls;    
		for(li = lm; li >= 1 && abs(v[li].x - xm) < dmin; li--);
		for(ls = lm; ls < v.size() && abs(v[ls].x - xm) < dmin; ls++);

		std::vector<Point> region; /*vector de puncte delimitat de distana d*/
		region = slice(v, li, ls);

		std::sort(region.begin(), region.end(), cmp_y);
		for(size_t i = 0; i < region.size(); i++)
			for(size_t j = 1; j < 8; j++)
				if(i + j < region.size())
					dmin =  std::min(dmin, dist(region[i], region[i+j]));
							
				
	return dmin;
	}
 
 
     
 
}
 
int main(){
	std::ifstream fin("cmap.in");
	std::ofstream fout("cmap.out");
	std::vector<Point> v;
	
	Point p;
	int n;
	
	fin >> n;
	for(int i = 0; i < n; i++){
		fin >> p.x >> p.y;
		v.push_back(p);
	}

	
	std::sort(v.begin(), v.end(), cmp_x);
	
	fout << std::setprecision(6) << std::fixed<< split_plane(v) << '\n';	
	return 0;   
}