18542. Tiro ao Alvo

Olá meus amigos nerds. Hoje vamos brincar de tiro ao alvo. Já que é isso que o problema 18542. Tiro ao Alvo nos pede para fazer. Mais especificamente, dadas as posições onde acertamos o alvo, e o tamanho de cada círculo do alvo, determinar quantos pontos nós fizemos. O número de pontos que um tiro alcança é igual ao número de círculos que ele ficou dentro.

Solução

O segredo desse problema é como contar o número de círculos que um tiro está dentro de forma eficiente. E isso não é muito difícil de fazer se lembrarmos que um ponto é interior a circunfência se:

x^2 + y^2 <= r^2

onde x e y são as coordenadas do ponto e r é o raio do círculo.

Testar essa relação para cada ponto e cada raio é ineficiente (O(C*T)). Entretanto, note que, se um ponto é interior a um círculo ele o será a todos os círculos com raios maiores. Então se ordenarmos os círculos pelos seus raios podemos utilizar busca binária para achar a posição em que o ponto deveria estar no array e dessa forma achar quantos círculos tem raio maior que o ponto. Assim:

pontos_ganhos(x,y) = C - posição de (x,y) no array de raios

onde C é o número de círculos.

Implementação

Note que o número de pontos pode não caber em uma variável do tipo int. Temos que usar um long long int (que tem pelo menos 64bits) para conseguir resolver o problema.

Observe, também, o uso da função lower_bound, que indica a posição do array que o valor passado como parâmetro deveria ocupar. lower_bound internamente implementa uma busca binária.

Por fim observe que a diferença entre dois ponteiros (pos - raios) resulta no número de elementos entre eles e não um endereço de memória.