Cod sursa(job #1617188)

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

struct Point{
	int x, y;
};


int x_cmp(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) return 0;
	else return -1;
}



int y_cmp(const void *a, const void *b){
	Point *p1 = (Point*) a;
	Point *p2 = (Point*) b;

	if(p1->y > p2->y) return 1;
	else if(p1->y == p2->y) return 0;
	else return -1;
}

/*
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(Point *v, int li, int ls){
	double 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){
				double d = dist(v[i], v[j]);
				if(d < minim) minim = d;
			}			

		}
	}

	return minim;
}

double split_plane(Point *xp, Point *yp, int li, int ls){
	
	if(ls - li <= 3)
		return brute_force(xp, li, ls);
	else{

			
		int lm = (li + ls) / 2; 
		int xm = xp[lm].x; /*dreapta care imparte planul*/

		double dmin1 = split_plane(xp, yp, li, lm);
		double dmin2 = split_plane(xp, yp, lm+1, ls);

		double 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 - yp[i].x) < dmin)
				region.push_back(yp[i]);

		for(size_t i = 0; i < region.size() - 1; i++){
			for(size_t k = i+1; k < region.size() && dist(yp[i], yp[k]) < dmin; k++)
				if(dist(yp[i], yp[k]) < dmin)
					dmin = dist(yp[i], yp[k]);
		
		}		

				
		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;
	}
	
	Point xp[n], yp[n];
	memcpy(xp, v, (n) * sizeof(Point));
	memcpy(yp, v, (n) * sizeof(Point));
	
	qsort(xp, n, sizeof(Point), x_cmp);
	qsort(yp, n, sizeof(Point), y_cmp);
	
	
	/*
	for(int i = 0; i < n; i++)
		std::cout << v[i] << std::endl;
	*/

	double dmin = split_plane(xp, yp, 0, n-1);
	fout.precision(8);
	fout << dmin << '\n';

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