Cod sursa(job #1617488)

Utilizator RobertSSamoilescu Robert RobertS Data 27 februarie 2016 14:23:19
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <fstream>
#include <vector>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>

#define INF 0x7fffff

struct Point{
	int x, y;
};


int x_cmp(Point p1, Point p2){
	return p1.x < p2.x;
}



bool y_cmp(Point p1, Point p2){
	return p1.y < p2.y;
}

/*
std::ostream& operator << (std::ostream& out, Point p){
	out << "("<< p.x << "," << p.y << ")";
	return out; 
}
*/


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 brute_force(std::vector<Point> v){
	double minim = INF; //initializez minimul;

	for(size_t i = 0; i < v.size()-1; i++){
		for(int j = i+1; j < v.size(); j++){
			double d = dist(v[i], v[j]);
			if(d < minim) minim = d;
						

		}
	}

	return minim;
}

double split_plane(std::vector<Point> v){
	
	if(v.size()<= 3){
		return brute_force(v);
	}else{
		int lm = (int)(v.size()/2); 
		int xm = v[lm].x; /*dreapta care imparte planul*/
		
		std::vector<Point> v1; v1.assign(v.begin(), v.begin() + lm + 1);
		std::vector<Point> v2; v2.assign(v.begin() + lm + 1, v.end());

		double dmin1 = split_plane(v1);
		double dmin2 = split_plane(v2);

		double dmin = std::min(dmin1, dmin2);
		
		std::vector<Point> reg; /*vector de puncte delimitat de distana d*/	
		for(int i = lm-1; i>= 0 && abs(v[i].x - xm) < dmin; i--)
			reg.push_back(v[i]);
		
		for(int i = lm; i < v.size() && abs(xm - v[i].x) < dmin; i++)
			reg.push_back(v[i]);

		
		std::sort(reg.begin(), reg.end(), y_cmp); /*sortez dupa y*/
		
		for(size_t i = 0; i < reg.size()-1; i++)
			for(size_t k = i+1; k < reg.size() && (abs(reg[i].y - reg[k].y) < dmin); k++)
				dmin = std::min(dist(reg[i], reg[k]), dmin);
								
		
			
		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 = 1; i <= n; i++){
		fin >> p.x >> p.y;
		v.push_back(p);
	}
	
	
	std::sort(v.begin(), v.end(), x_cmp);

	double dmin = split_plane(v);
	fout.precision(8);
	fout << dmin << '\n';

	fin.close();
	fout.close();
	return 0;	
}