Solução Viagem Espacial

Solução por Rogério Júnior

O lugar geométrico dos pontos (x, y) de uma reta que passa pelos pontos ($X_1, Y_1$) e ($X_2, Y_2$) é definido pela lei de formação $y=ax +b$, onde $a= \frac{Y_2 - Y_1}{X_2 - X_1}$ e $b = - aX_1 + Y_1$. Um tiro acerta um asteroide se ele atravessar o círculo determinado pela sua circunferência, ou seja, se a distância entre o centro da circunferência e a reta determinada pelo tiro for menor que o raio do asteroide. Sabemos que a distância $d$ do ponto ($X_C$, $Y_C$) é igual a $\frac{\mid p \times q \mid}{\sqrt{p^2+q^2}}$, onde $p=Y_C - aX_C + b$ e $q=X_C - (Y_C-b)/a$. Se $Y_1=Y_2$, então a reta é paralela ao eixo das abscissas e basta checar se o valor de sua ordenada se encontra entre $Y_C-R$ e $Y_C+R$. Se $X_1=X_2$, então a reta é paralela ao eixo das ordenadas e basta checar se o valor de sua abscissa se encontra entre $X_C-R$ e $X_C+R$. Além disso, se $p=q=0$ (o ponto da reta usado como referência é o centro do asteroide), a distância entre a reta e o ponto é zero. Assim, basta declararmos uma variável resp (de valor inicial igual a zero) e, para cada tiro, checar se ele acertou o asteroide (se a distância do centro do asteroide até a reta determinada por ele é menor que o raio $R$), adicionando uma unidade a resp caso ele tenha acertado.

É muito importante, nesse problema, ressaltar como fazemos comparações seguras entre variáveis do tipo double. Se usássemos simples comando "if(d<=r) resp++;" para descobrirmos se a distância do ponto à reta é menor que o raio, nosso programa iria ganhar apenas 75 dos 100 pontos da OBI, com resposta errada nos demais casos. Ocorre que operações com double envolvem várias aproximações do computador, e este arredondamento pode fazer com que números que devia ser iguais, fiquem diferentes, ou como no caso, que um número que não devei superar outro, supere. Por isso, sempre usamos uma margem de erro muito pequena na comparação. Não iremos verificar se d<=r, mas sim se d<=r+delta, onde delta será uma double pequena que iremos definir, e será nossa margem de erro. Os valores das coordenadas são menores que 1000, logo, ainda restam mais de 10 casas decimais da double depois do ponto flutuante. Desse modo, nossa margem de segurança pode ser da ordem de $10^{-10}$, e definiremos delta como 0.00000000001, que é bem mais preciso que a menor distância que pode aparecer no problema, que é da ordem de $\frac{1}{1000}$ por trabalharmos apenas com inteiros menores que 1000, o que não incluirá, portanto, distâncias realmente maiores que o raio do asteroide. Segue o código para melhor entendimento: