Problema ELEVADOR (SPOJ Brasil)

Luiz Santos, Outubro de 2012

O problema a ser resolvido neste tutorial é o Elevador. É um problema fácil de Geometria Computacional.

Resumo do enunciado

Dadas as dimensões L (largura) e C (comprimento) de uma caixa retangular, e os raios R1 e R2 de duas circunferências, deve-se determinar se as duas circunferências podem ser colocadas na caixa. Imprimimos ’S' se for possível, e ‘N’ caso contrário. Observação: o problema trata de cilindros em um elevador, mas, como as alturas não são dadas, o problema se reduz a duas dimensões.

Implementação da solução

Podemos resolver diretamente alguns casos com uma verificação inicial simples: a menor dimensão da caixa, seja ela a largura ou a altura, deve ser suficientemente grande para que a circunferência de maior diâmetro possa ser colocada lá.

Devemos agora colocar as duas circunferências lado a lado, de modo que elas se tangenciam e tangenciam uma mesma aresta do retângulo dado. É nesta posição que elas ocupam o menor espaço possível, e a distância entre os centros é mínima. Seja R o segmento que liga os centros das circunferências (R = R1 + R2). É fácil perceber que conseguimos construir um trapézio ligando os centros das circunferências à aresta que foi tangenciada. Desse trapézio, extraímos um triângulo retângulo cuja hipotenusa é justamente R.

Agora, podemos afastar as duas circunferências o máximo possível, colocando-as em extremidades diagonalmente opostas da caixa. Conseguimos construir um segundo trapézio ligando os centros a uma mesma aresta, e dele extrair um segundo triângulo retângulo de hipotenusa R'. O comprimento de R' é a distância máxima, dentro da caixa, entre os centros das circunferências.

Se R' > R, os círculos cabem na caixa, e respondemos ’S'. Se R' < R, temos que na situação de afastamento máximo existe uma interseção entre os círculos , ou seja, os círculos não cabem na caixa. Assim, respondemos ‘N’.

Detalhes de implementação

É altamente recomendado NÃO olhar o código antes de tentar a sua própria implementação.

Para calcular R', basta determinar as dimensões do “triângulo máximo”. Sejam A e B os catetos desse retângulo, podemos definir:

• A = L – (R1 + R2)
• B = C – (R1 + R2)

O código foi escrito de modo a evitar operações em ponto flutuante (float ou double). Além de serem mais caras que operações com inteiros, não precisaremos nos preocupar com precisão ou comparações. No entanto, tenha em mente que esta otimização nem sempre é possível.

#include <iostream>
#include <cmath>
using namespace std;

int main () {
    cin.sync_with_stdio (false);
    
    while (true) {
        int l, c, r1, r2; // Largura, Comprimento, Raio1 e Raio2
        
        cin >> l >> c >> r1 >> r2;
        if (!(l || c || r1 || r2)) break;
        
        if (min(l, c) < 2*max(r1, r2))
            cout << "N\n";
        else {
            int R = r1+r2;
            int a = l - R;
            int b = c - R; // R' = sqrt (a*a + b*b);
            
            if (a*a + b*b < R*R) // Comparamos com R*R para evitarmos a raiz quadrada.
                cout << "N\n";
            else
                cout << "S\n";
        }
    }
    return 0;
}