Cod sursa(job #1172785)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 18 aprilie 2014 00:16:18
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2 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 compare_x(point a, point b){
	return a.x <= b.x;
}

int compare_y(point a, point b){
	return a.y <= 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];
	}
	sort(submult, submult+len, 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 inline find(int left, int right){
	double d, delta;
	int i, j;
	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));
	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 << sqrt(find(0, n-1));
	return 0;
}