Cod sursa(job #964437)

Utilizator sorin2kSorin Nutu sorin2k Data 20 iunie 2013 23:00:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 4.25 kb
#include <fstream>
#include <iostream>
#include <math.h>
#include <cstdlib>
using namespace std;
struct point{
	int x, y;
	void to_string(){
		cout<<x<<" "<<y<<"\n";
	}
};
double draw_line(point points[], int number_of_points, int start, int end, int *m){
	
	*m = (end - start) / 2 + start;
	// daca au acelasi x iau urmatoarele 2
	//cout<<start<<" "<<end<<"\n";
	//cout<<"M: "<<*m<<"\n";
	if (points[*m].x != points[(*m)+1].x){
		//cout<<"am linia "<<(points[(*m)+1].x - points[*m].x)/2 + points[*m].x<<"\n";
		return (points[(*m)+1].x - points[*m].x)/2 + points[*m].x;
	}else{
		(*m)++; // ar putea fi o problema in cazul in care toate din intervalul meu sunt la fel :(
		while(points[*m].x == points[(*m)+1].x){
			(*m)++;
		}
		return (points[(*m)+1].x - points[*m].x)/2 + points[*m].x;
	}
}
int power(int diff){
	return diff*diff;
}
double distance(point points[], int start, int end){
	return sqrt(power(points[start].x - points[end].x) + power(points[start].y - points[end].y));
}
double get_min(point points[], int start, int end){
	
	if (end-start+1 == 3){
		// calculez minimul dintre 3 pct
		double d1 = distance(points, start, end);
		double d2 = distance(points, start, start+1);
		if (d1 < d2){
			return fmin(d1, distance(points, start+1, end));
		}else{
			return fmin(d2,distance(points, start+1, end));
		}
	}else{
		// calculez distanta dintre doua puncte
		return distance(points, start, end);
	}
	
}
int compare (const void * a, const void * b){
	point fst = *(point *)a;
	point snd = *(point *)b;
	if (fst.x < snd.x){
		return -1;
	}else{ 
		if (fst.x == snd.x)
			if(fst.y < snd.y)
				return -1;
			else
				return 1;
		else
			return 1;
	}
}
int compare2(const void *a, const void *b){

	point fst = *(point *)a;
	point snd = *(point *)b;
	if (fst.y < snd.y)
		return -1;
	return 1;
}
void set_before_and_after(point points[], int number_of_points, 
	double line, double dmin,int *before, int*after, int m){
	
	int i;
	//cout<<"m "<<m<<"\n";
	//cout<<"line-dmin "<<line-dmin<<"\n";
	for(i = m; i >= 0; i--){
		if(points[i].x > line-dmin)
			continue;
		else
			break;
	}
	*before = i + 1;
	for(i = m+1; i < number_of_points; i++){
		if(points[i].x < line + dmin)
			continue;
		else
			break;
	}
	*after = i - 1;
	//cout<<" before & after \n";
	//cout<<*before<<" "<<*after<<"\n";
}
double combine(point points[],int number_of_points,double line,double dmin, int m){
	
	int before, after, i, j;
	double dist, mini;
	set_before_and_after(points,number_of_points,line,dmin,&before,&after,m);
	if (before > after){
		// nu mai am ce distante sa verific intre drepte
		return dmin;
	}else{
		
		int length = after-before + 1;
		point copy[length];
		for(i = 0; i < length; i++){
			copy[i].x = points[before+i].x;
			copy[i].y = points[before+i].y;
		}
		qsort(copy,length,sizeof(point),compare2);
		mini = distance(copy,0,1);
		for(i = 0; i < length; i++){	
			for(j = 1; j < 7; j++){
				// urmatoarele 7 puncte le compar
				double d = distance(copy,i,i+j);
				if (i + j < length &&  d < mini){
					mini = d;
				}
			}
		}
		//cout<<"mini "<<mini<<"\n";
		return fmin(mini,dmin);
	}
}
double recursivity(point points[], int number_of_points, int start, int end){
	
	int m;
	if (end - start + 1 <= 3){
		// opresc recursivitatea si aflu distanta minima dintre 3 puncte
		return get_min(points,start,end);
	}
	// trag dreapta si fac recursivitate pe intervale
	double line = draw_line(points,number_of_points, start, end,&m);
	double d1 = recursivity(points,number_of_points,start, m);
	double d2 = recursivity(points,number_of_points,m+1, end);
	//cout<<"line "<<line<<"\n";
	//cout<<"d1 "<<d1<<" d2 "<<d2<<"\n";
	//cout<<"minimul dintre d1 si d2 este "<<fmin(d1,d2)<<"\n";
	double min = combine(points,number_of_points,line,fmin(d1,d2),m);
	return min;
}
int main(){

	ifstream fin("cmap.in");
	ofstream fout("cmap.out");
	int number_of_points, i;
	fin>>number_of_points;
	point points[number_of_points];
	for(i = 0; i < number_of_points; i++){
		fin>>points[i].x>>points[i].y;
	}
	qsort(points, number_of_points,sizeof(point), compare);
	//for(i = 0; i < number_of_points; i++){
	//	cout<<points[i].x<<" "<<points[i].y<<"\n";
	//} 
	cout.precision(8);
	fout.precision(8);
	fout<<recursivity(points,number_of_points, 0, number_of_points - 1);
	//cout<<recursivity(points,number_of_points, 0, number_of_points - 1);
	return 0;
}