Outro dia vi um jeito alternativo de implementar o algoritmo de divisão e conquista para encontrar o par mais próximo, e achei legal. Deixa então eu contar para vocês.
A implementação evita aquela ordenação indireta nas Y-coordenadas (ou seja, nos livramos do vetor a da implementação vista em aula).
Para tanto, a descrição do algoritmo recursivo fica um pouco diferente: ele receberá os pontos, dados pelos vetores X[p..r] e Y[p..r], ordenador pelas X-coordenadas, e além de devolver a distância mínima entre pontos neste trecho dos vetores, ele também rearranja os vetores X[p..r] e Y[p..r] para que fiquem ordenados por Y-coordenada.
Ou seja, ao mesmo tempo que o algoritmo busca a distância mínima, ele ordena os pontos pela Y-coordenada... O divide volta a ser trivial: consiste em apenas calcular o índice do meio. E o combina, antes de fazer o que faz, tem que reorganizar os pontos para que fiquem ordenados por Y-coordenada. Só que... a recursão já fez isso para os pontos da esquerda e para os pontos da direita... então o combina precisa apenas intercalar os pontos da esquerda e da direita... o que dá para fazer em tempo linear!
Entenderam? Legal, né?
Só que... se quisermos devolver os pontos que atingem a distância mínima, temos que tomar cuidado, pois os pontos estão mudando de lugar...
Até,
Cris