O problema do par de pontos mais próximos em um plano é um desafio clássico em geometria computacional, frequentemente resolvido com o paradigma de divisão e conquista. Este método envolve dividir recursivamente o conjunto de pontos, calcular distâncias mínimas em subconjuntos e combinar os resultados considerando pontos próximos à linha de divisão.

Problemas Relacionados

Consideremos algumas variações de problemas que aplicam esta técnica:

• P1257: Versão básica do par de pontos mais próximos, onde uma abordagem por força bruta pode ser eficaz.
• P1429: Versão aprimorada, exigindo uma implementação otimizada de divisão e conquista para superar soluções ineficeintes.
• P7883: Versão ainda mais robusta, projetada para eliminar heurísticas não determinísticas e garantir eficiência.
• P4423: Envolvendo o cálculo do menor triângulo entre três pontos, uma extensão natural do problema.

Algoritmo de Divisão e Conquista

O algoritmo ordena os pontos por coordenada x, divide recursivamente o conjunto, e após calcular as distâncias mínimas nas metades esquerda e direita, considera apenas pontos dentro de uma faixa estreita em torno da linha de divisão. Estes pontos são então ordenados por coordenada y para otimizar a busca de pares próximos, resultando em uma complexidade de tempo de O(n log n) com ordenação por divisão e conquista.

Exemplos de Código

A seguir, implementações em C++ para os problemas mencionados, com variáveis e estruturas renomeadas para clareza, mantendo a correção algorítmica.

Para P1257 e P1429

#include<bits/stdc++.h>
#define tipo_dist double
using namespace std;
const int MAX_PONTOS = 1e6 + 10;
int total_pontos;
int indices_temp[MAX_PONTOS];
struct Ponto { int coord_x, coord_y; } pontos[MAX_PONTOS];

tipo_dist calcular_distancia(int idx1, int idx2) {
    int x1 = pontos[idx1].coord_x, y1 = pontos[idx1].coord_y;
    int x2 = pontos[idx2].coord_x, y2 = pontos[idx2].coord_y;
    return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
}

bool comparar_por_x(Ponto a, Ponto b) {
    if (a.coord_x == b.coord_x) return a.coord_y < b.coord_y;
    return a.coord_x < b.coord_x;
}

bool comparar_por_y(int idx_a, int idx_b) {
    return pontos[idx_a].coord_y < pontos[idx_b].coord_y;
}

tipo_dist resolver_divisao(int inicio, int fim) {
    tipo_dist dist_minima = 1e18;
    if (inicio == fim) return dist_minima;
    if (inicio + 1 == fim) return calcular_distancia(inicio, fim);
    
    int meio = (inicio + fim) >> 1;
    tipo_dist dist_esq = resolver_divisao(inicio, meio);
    tipo_dist dist_dir = resolver_divisao(meio + 1, fim);
    dist_minima = min(dist_esq, dist_dir);
    
    int contagem = 0;
    for (int i = inicio; i <= fim; i++) {
        if (fabs(pontos[meio].coord_x - pontos[i].coord_x) < dist_minima)
            indices_temp[++contagem] = i;
    }
    sort(indices_temp + 1, indices_temp + contagem + 1, comparar_por_y);
    
    for (int i = 1; i <= contagem; i++) {
        for (int j = i + 1; j <= contagem; j++) {
            if (pontos[indices_temp[j]].coord_y - pontos[indices_temp[i]].coord_y >= dist_minima) break;
            dist_minima = min(dist_minima, calcular_distancia(indices_temp[i], indices_temp[j]));
        }
    }
    return dist_minima;
}

int main() {
    scanf("%d", &total_pontos);
    for (int i = 1; i <= total_pontos; i++)
        scanf("%d%d", &pontos[i].coord_x, &pontos[i].coord_y);
    sort(pontos + 1, pontos + total_pontos + 1, comparar_por_x);
    printf("%.4lf", resolver_divisao(1, total_pontos));
    return 0;
}

Para P7883

#include<bits/stdc++.h>
#define tipo_dist double
using namespace std;
const int MAX_PONTOS = 1e6 + 10;
int total_pontos;
int indices_temp[MAX_PONTOS];
struct Ponto { int coord_x, coord_y; } pontos[MAX_PONTOS];

tipo_dist calcular_distancia(int idx1, int idx2) {
    int x1 = pontos[idx1].coord_x, y1 = pontos[idx1].coord_y;
    int x2 = pontos[idx2].coord_x, y2 = pontos[idx2].coord_y;
    return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
}

bool comparar_por_x(Ponto a, Ponto b) {
    if (a.coord_x == b.coord_x) return a.coord_y < b.coord_y;
    return a.coord_x < b.coord_x;
}

bool comparar_por_y(int idx_a, int idx_b) {
    return pontos[idx_a].coord_y < pontos[idx_b].coord_y;
}

tipo_dist resolver_divisao(int inicio, int fim) {
    tipo_dist dist_minima = 1e18;
    if (inicio == fim) return dist_minima;
    if (inicio + 1 == fim) return calcular_distancia(inicio, fim);
    
    int meio = (inicio + fim) >> 1;
    tipo_dist dist_esq = resolver_divisao(inicio, meio);
    tipo_dist dist_dir = resolver_divisao(meio + 1, fim);
    dist_minima = min(dist_esq, dist_dir);
    
    int contagem = 0;
    for (int i = inicio; i <= fim; i++) {
        if (fabs(pontos[meio].coord_x - pontos[i].coord_x) < dist_minima)
            indices_temp[++contagem] = i;
    }
    sort(indices_temp + 1, indices_temp + contagem + 1, comparar_por_y);
    
    for (int i = 1; i <= contagem; i++) {
        for (int j = i + 1; j <= contagem; j++) {
            if (pontos[indices_temp[j]].coord_y - pontos[indices_temp[i]].coord_y >= dist_minima) break;
            dist_minima = min(dist_minima, calcular_distancia(indices_temp[i], indices_temp[j]));
        }
    }
    return dist_minima;
}

int main() {
    scanf("%d", &total_pontos);
    for (int i = 1; i <= total_pontos; i++)
        scanf("%d%d", &pontos[i].coord_x, &pontos[i].coord_y);
    sort(pontos + 1, pontos + total_pontos + 1, comparar_por_x);
    printf("%.0lf", pow(resolver_divisao(1, total_pontos), 2));
    return 0;
}

Para P4423

#include<bits/stdc++.h>
#define tipo_dist double
using namespace std;
const int MAX_PONTOS = 1e6 + 10;
int total_pontos;
int indices_temp[MAX_PONTOS];
struct Ponto { int coord_x, coord_y; } pontos[MAX_PONTOS];
tipo_dist resposta_minima = 1e18;

tipo_dist calcular_distancia(int idx1, int idx2) {
    int x1 = pontos[idx1].coord_x, y1 = pontos[idx1].coord_y;
    int x2 = pontos[idx2].coord_x, y2 = pontos[idx2].coord_y;
    return sqrt(1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2));
}

bool comparar_por_x(Ponto a, Ponto b) {
    if (a.coord_x == b.coord_x) return a.coord_y < b.coord_y;
    return a.coord_x < b.coord_x;
}

bool comparar_por_y(int idx_a, int idx_b) {
    return pontos[idx_a].coord_y < pontos[idx_b].coord_y;
}

void resolver_triangulo(int inicio, int fim) {
    if (inicio == fim) return;
    int meio = (inicio + fim) >> 1;
    resolver_triangulo(inicio, meio);
    resolver_triangulo(meio + 1, fim);
    
    int contagem = 0;
    for (int i = inicio; i <= fim; i++) {
        if (fabs(pontos[meio].coord_x - pontos[i].coord_x) < resposta_minima / 2.0)
            indices_temp[++contagem] = i;
    }
    sort(indices_temp + 1, indices_temp + contagem + 1, comparar_por_y);
    
    for (int i = 1; i <= contagem; i++) {
        for (int j = i + 1; j <= contagem; j++) {
            if (pontos[indices_temp[j]].coord_y - pontos[indices_temp[i]].coord_y >= resposta_minima / 2.0) break;
            for (int k = j + 1; k <= contagem; k++) {
                if (pontos[indices_temp[k]].coord_y - pontos[indices_temp[i]].coord_y >= resposta_minima / 2.0) break;
                tipo_dist perimetro = calcular_distancia(indices_temp[i], indices_temp[j]) +
                                      calcular_distancia(indices_temp[i], indices_temp[k]) +
                                      calcular_distancia(indices_temp[k], indices_temp[j]);
                resposta_minima = min(resposta_minima, perimetro);
            }
        }
    }
}

int main() {
    scanf("%d", &total_pontos);
    for (int i = 1; i <= total_pontos; i++)
        scanf("%d%d", &pontos[i].coord_x, &pontos[i].coord_y);
    sort(pontos + 1, pontos + total_pontos + 1, comparar_por_x);
    resolver_triangulo(1, total_pontos);
    printf("%.6lf", resposta_minima);
    return 0;
}