Problema FUROS (SPOJ Brasil)

Gabriel Poesia, Outubro de 2012

Neste tutorial, resolveremos o problema “Cubra os furos”, do SPOJ Brasil. Este é um problema de nível fácil sobre Geometria Computacional. É um bom problema para se introduzir ao assunto que, em geral, costuma ser cobrado em um nível muito maior em competições.

Resumo do enunciado

Na entrada, são dados diversos pontos, cada um deles representando um furo, cujo diâmetro é fixo (5mm). Seu objetivo é escrever um programa que determina qual o menor diâmetro de um círculo que, se centrado em um dos furos, cobriria todos os furos.

Observação 1 – O diâmetro do círculo da resposta

Suponha que você saiba que o círculo está centrado em um determinado ponto. O círculo tem que cobrir todos os pontos, mas é suficiente que ele cubra o ponto mais distante de seu centro, pois assim ele já estará cobrindo todos os outros. O raio mínimo deste círculo para cobrir o ponto mais distante seria a distância entre os centros, somada ao raio do furo a ser coberto, que é 5mm (como diz o enunciado). Assim, bastaria calcular a distância do centro do círculo a todos os outros centros de furos, o que pode ser feito em tempo linear, e somar a 5mm para achar o raio mínimo do círculo. Como a resposta pede o diâmetro, a resposta seria 2*R.

Observação 2 – Tamanho da entrada

Inicialmente, você não sabe qual é o furo em que o círculo estará centrado. Mas as restrições do problema dizem que N (o número de furos) é no máximo 1000. Logo, você poderia tentar todos os N pontos, e ver qual deles daria o menor círculo. A complexidade deste algoritmo seria O(n² ), o que é aceitável para os limites do problema.

Implementação da solução

A solução pode ser implementada da seguinte forma: após a leitura da entrada, computa-se as distâncias entre todos os pares de pontos. Depois, para cada ponto, computa-se a maior distância entre o ponto escolhido e todos os outros. O ponto que tiver a menor distância máxima computada será o centro do círculo da resposta. Para obter o diâmetro, deve-se somar o raio de um furo (2.5mm) na distância encontrada, e multiplicá-la por 2.

Detalhes de implementação

Em caso de TLE (Tempo Limite Excedido), as seguintes otimizações na implementação da ideia podem ser úteis:

1. Tente usar ‘'stdio.h’‘, biblioteca C, ao invés da ’‘iostream’‘, C++. Sem otimizações no uso da ’‘iostream’‘, a ’‘stdio.h’‘ geralmente é muito mais eficiente.
2. Ao invés de calcular as distâncias usando ponto flutuante (double), você pode fazer todos os cálculos intermediários com números inteiros, e não tirar raízes quadradas. Isso porque se o quadrado de uma distância é maior que o quadrado de outra, obviamente a primeira distância é maior. Assim, você pode fazer todas as comparações com os quadrados das distâncias. No final, ao exibir a resposta, você então tira a raiz quadrada do valor encontrado e faz as devidas modificações.

Se sua implementação está errando por 1 nos casos de exemplo, não se preocupe. Problemas que trabalham ponto flutuante são suscetíveis a este tipo de problema de precisão, e o resultado de um mesmo código pode variar com a máquina que está executando o programa. Assim, neste caso, sua resposta provavelmente estará certa no servidor do SPOJ.

O seguinte código-fonte implementa esta solução. Recomendamos que, antes de consultá-lo, você tente implementar sua própria versão da solução.

#include <cstdio>
#include <cmath>

using namespace std;

#define MAXN 1000 //número máximo de pontos na entrada

int pontos[MAXN][2]; //pontos[i][0] = a posição X do i-ésimo ponto, pontos[i][1] a posição y
int N; //número de pontos

//calcula a distância entre os pontos i e j da matriz pontos
double calcular_distancia(int i, int j) {
    return sqrt(pow(pontos[i][0] - pontos[j][0], 2) + pow(pontos[i][1] - pontos[j][1], 2));
}

//calcula e retorna a resposta para a instância atual do problema
double menor_diametro() {

    double menor_raio = INFINITY; //raio do menor círculo encontrado que cobriria todos os furos
    
    for(int i = 0; i < N; i++) {
    double maior_distancia = 0;

    for(int j = 0; j < N; j++) {

        double d = calcular_distancia(i, j);
        
        if(d > maior_distancia) {
        maior_distancia = d;
        }
    }

    if(maior_distancia < menor_raio) {
        menor_raio = maior_distancia;
    }
    }

    return menor_raio * 2 + 5;
}

int main() {

    int casoTeste = 1;

    while(true) {
    
    scanf("%d", &N);
    
    if(N == 0) //fim da entrada
        break;

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &pontos[i][0], &pontos[i][1]);
    }

    printf("Teste %d\n", casoTeste);
    printf("%.0lf\n\n", menor_diametro());

    casoTeste++;
    }

    return 0;
}