Cod sursa(job #1617018)

Utilizator RobertSSamoilescu Robert RobertS Data 27 februarie 2016 12:27:07
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>

struct Point{
	int x, y;
};


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;
	
}

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


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

float brute_force(Point *v, int li, int ls){
	float minim = dist(v[li], v[ls]); //initializez minimul;
	
	for(int i = li; i < ls; i++){
		for(int j = i+1; j <= ls; j++){
			if(li != ls){
				float d = dist(v[i], v[j]);
				if(d < minim) minim = d;
			}			

		}
	}

	return minim;
}

float split_plane(Point *v, int li, int ls){
	
	if(ls - li <= 3)
		return brute_force(v, li, ls);
	else{
		int lm = (li + ls) / 2; 
		int xm = v[lm].x; /*dreapta care imparte planul*/

		float dmin1 = split_plane(v, li, lm);
		float dmin2 = split_plane(v, lm+1, ls);

		float dmin = std::min(dmin1, dmin2);
		
		std::vector<Point> region; /*vector de puncte delimitat de distana d*/
		for(int i = li; i <= ls; i++)
			if(abs(xm - v[i].x) < dmin)
				region.push_back(v[i]);

		for(size_t i = 0; i < region.size() - 1; i++){
			for(size_t k = i+1; k < region.size() && abs(v[i].y - v[k].y) < dmin; k++)
				if(abs(v[i].y - v[k].y) < dmin)
					dmin = abs(v[i].y - v[k].y);
		
		}		

				
		return dmin;
	}


	

}

int main(){
	
	std::ifstream fin("cmap.in");
	std::ofstream fout("cmap.out");

	int n;
	fin >> n;
	
	
	Point v[n];

	for(int i = 0; i < n; i++){
		fin >> v[i].x >> v[i].y;
	}
	
	qsort(v,  n, sizeof(Point), compare);
	
	/*
	for(int i = 0; i < n; i++)
		std::cout << v[i] << std::endl;
	*/

	float dmin = split_plane(v, 0, n-1);
	fout.precision(8);
	fout << dmin << '\n';

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