Cod sursa(job #1172795)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 18 aprilie 2014 00:46:52
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#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 inline compare_x(point a, point b){
	return a.x <= b.x;
}

int inline compare_y(point a, point b){
	return a.y <= b.y;
}

double inline dist(point a, point b){
	return sqrt(pow((double)(b.x-a.x),2.)+ 
			pow((double)(b.y-a.y),2.));
}

double inline combine(int i, int j, double delta){
	int len = j - i + 1;
	double v;
	for(int k = 0; k < len; k++){
		submult[k] = numbers[k+i];
	}
	sort(submult, submult+len, compare_y);
	for(int k = 0; k < len; k++){
		// optimizare pt cache 
		point *kk = submult+k;
		for(int l = 1; l <= 7; l++){
			if(k+l >= len) break;
			if(delta > (v = dist(*kk, *(kk+l))))
				delta = v;
		}
	}
	return delta;
}

double inline find(int left, int right){
	double d, delta, v;
	int i, j;
	int len = right-left+1;
	if(len == 3){
		double d1 = dist(numbers[left], numbers[left+1]);
		double d2 = dist(numbers[left], numbers[left+2]);
		double d3 = dist(numbers[left+1], numbers[left+2]);
		if(d1 > d2)
			d1 = d2;
		if(d1 > d3)
			d1 = d3;
		return d1;
	}
	if(len == 2)
		return dist(numbers[left], numbers[left+1]);
		
	d = numbers[left + len/2-1].x + (numbers[left + len/2].x - numbers[left + len/2 - 1].x)/2.;
	delta = find(left, left+len/2-1);
	if(delta > (v = find(left + len/2, right)))
		delta = v;
	i = left + len/2 -1;
	while(i >= left && ((d - numbers[i].x) <= delta))
		i--;
	
	j = left + len/2;
	while(j <= right && ((numbers[j].x - d) <= delta))
			j++;

	delta = combine(i+1, j-1, 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 */
	sort(numbers, numbers+n, compare_x);
	
	fout << setprecision(6) << std::fixed << find(0, n-1);
	return 0;
}