Cod sursa(job #1172772)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 18 aprilie 2014 00:02:57
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <iomanip>
#define max 100001

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

int n;

struct point{
	int x, y;
};

typedef struct point point;

point numbers[max];
point submult[max];

int compare_x(const void *a, const void *b){
	return ((point*)a)->x - ((point*)b)->x;
}

int compare_y(const void *a, const void *b){
	return ((point*)a)->y - ((point*)b)->y;
}

double dist(int a, int b, int who){	// who = 0 pt numbers 1 pt submult
	if (who == 0)
		return (double)(numbers[b].x-numbers[a].x) * (double)(numbers[b].x-numbers[a].x) + 
				(double)(numbers[b].y-numbers[a].y) * (double)(numbers[b].y-numbers[a].y);
	return (double)(submult[b].x-submult[a].x) * (double)(submult[b].x-submult[a].x) + 
			(double)(submult[b].y-submult[a].y) * (double)(submult[b].y-submult[a].y);
}

double combine(int i, int j, double delta){
	int len = j - i + 1;
	for(int k = 0; k < len; k++){
		submult[k] = numbers[k+i];
	}
	qsort(submult, len, sizeof(point), compare_y);
	for(int k = 0; k < len; k++){
		for(int l = 1; l <= 7; l++){
			if(k+l >= len) break;
			delta = min(delta, dist(k, k+l,1));
		}
	}
	return delta;
}

double find(int left, int right){
	double d, delta;
	int st, dr, i, j, mij = (right+left)/2;
	int len = right-left+1;
	if(len == 3)
		return min(dist(left, left+1,0), min(dist(left, left+2,0), dist(left+1, left+2,0)));
	if(len == 2)
		return dist(left, left+1,0);
		
	d = numbers[left + len/2-1].x + (numbers[left + len/2].x - numbers[left + len/2 - 1].x)/2.;
	delta = min(find(left, left+len/2-1), find(left + len/2, right));
	st = left + len/2 -1;
	while(st >= left && ((d - numbers[st].x) <= delta))
		st--;
	st++;
	dr = left + len/2;
	while(dr <= right && ((numbers[dr].x - d) <= delta))
			dr++;
	dr--;
	for(i = st; i <= mij; i++){
		for(j = mij+1; j <= dr; j++){
			double aux = dist(i,j,0);
			delta = min(aux, delta);
		}
	}
	
	return delta;
}


int main(){
	point p;
	fin >> n;
	for(int i = 0; i < n; i++){
			fin >> p.x >> p.y;
			numbers[i] = p;
	}
	/* sorted after x */
	qsort(numbers, n, sizeof(numbers[0]), compare_x);
	
	fout << setprecision(6) << std::fixed << sqrt(find(0, n-1));
	return 0;
}