distanza minima nel piano

[CuriousCI]

Dati $(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)$ con $x_i, y_i \in \mathbb{R}$ scrivere lo pseudocodice di un algoritmo che trova la distanza minima fra due punti nel piano in $O(n log^2(n))$

[CarloDaRomadev]

def min_dist_piano(I : insieme di punti ordinati per la prima componente) //l'operazione di ordinamento in base al valore della prima componente può essere svolta in una funzine a parte ed ha costo = O(n(log(n)))
	if len(I) == 0{return 0}
	if len(I) == 1{return 0}
	if len(I) == 2{return dist(I[0], I[1])}
	if len(I) == 3{return min( dist(I[0],I[1]), dist(I[1],I[2]), dist(I[0],I[2]) )}
	m = len(I) / 2
	R = min_dist_piano(I[0 : m])
	L = min_dist_piano(I[m+1 : (len(I)-1)])

	lambda = min(R,L)
	fascia = []
	for x in I{
		if m-lambda <= x <= m+lambda{
			fascia.append(x)
		}
	}
	ordina fascia per array					//l'operazione ha costo = O(n(log(n)))

	S = NULL
	for w in len(fascia){
		for i in range 1-7{
			S = min(S, dist(I[w],I[w+i]))
		}
	}

	return min(S,L,R)