Cod sursa(job #1617503)

Utilizator RobertSSamoilescu Robert RobertS Data 27 februarie 2016 14:41:13
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 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 dmin = std::min(split_plane(v1), split_plane(v2));
		
		std::vector<Point> reg; /*vector de puncte delimitat de distana d*/	
		int linf, lsup;
		for(linf = lm; linf>= 0 && abs(v[linf].x - xm) < dmin; linf--)
		
		for(int lsup = lm; lsup < v.size() && abs(xm - v[lsup].x) < dmin; lsup++)

		reg.assign(v.begin()+linf, v.begin()+lsup+1);
		std::sort(reg.begin(), reg.end(), y_cmp);
		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;	
}