Solução por Rogério Júnior
O lugar geométrico dos pontos (x, y) de uma reta que passa pelos pontos () e () é definido pela lei de formação , onde e . 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 do ponto (, ) é igual a , onde e . Se , então a reta é paralela ao eixo das abscissas e basta checar se o valor de sua ordenada se encontra entre e . Se , então a reta é paralela ao eixo das ordenadas e basta checar se o valor de sua abscissa se encontra entre e . Além disso, se (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 ), 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 , e definiremos delta como 0.00000000001, que é bem mais preciso que a menor distância que pode aparecer no problema, que é da ordem de 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <cmath> | |
#include <algorithm> | |
using namespace std; | |
int n, resp; | |
double xc, yc, r, delta=0.00000000001; | |
int main(){ | |
// leio os valores de n, xc, yc e r | |
scanf("%d %lf %lf %lf", &n, &xc, &yc, &r); | |
// para cada tiro | |
for(int i=1; i<=n; i++){ | |
// leio os dos pontos que o determinam | |
double x1, y1, x2, y2; | |
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); | |
// se a reta é paralela ao eixo das abscissas | |
if(x1==x2){ | |
// a distância é a diferença etre as coordenadas x | |
// da reta e do centro do asteroide | |
if(abs(xc-x1)<=r) resp++; | |
continue; | |
} | |
// se a reta é paralela ao eixo das ordenadas | |
if(y1==y2){ | |
// a distância é a diferença etre as coordenadas y | |
// da reta e do centro do asteroide | |
if(abs(yc-y1)<=r) resp++; | |
continue; | |
} | |
// se não, calculo o termos da equação comum da distância | |
double a=(y2-y1)/(x2-x1), b=-a*x1+y1; | |
double p=yc-a*xc-b, q=xc-(yc-b)/a; | |
//se o ponto da reta usado como referência for o centro do asteroide | |
if(p==q && p==0){ | |
// então o tiro acertou o alvo | |
resp++; | |
continue; | |
} | |
// se não, calculo a distância normalmente | |
double d=abs(p*q)/sqrt(p*p+q*q); | |
// e se ela for menor que o raio, a reta cprta o círculo | |
if(d<=r+delta) resp++; | |
} | |
// após a leitura da entrada, imprimo o valor de resp | |
printf("%d\n", resp); | |
return 0; | |
} |