Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2432
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2432
Tiro ao Alvo
Por OBI - Olimpíada Brasileira de Informática 2013 
Brazil
Timelimit: 1
Recentemente Juquinha ganhou de aniversário um joguinho bem clássico: Tiro ao Alvo. Ele arrumou um ótimo lugar em seu quarto para se divertir com o jogo, porém após ler todas as regras do jogo ele percebeu que precisa da sua ajuda para calcular a pontuação obtida.
Segundo as regras, o alvo do jogo é composto por C círculos, todos centrados na origem (0,0). Juquinha atira T vezes e após cada tiro informa suas coordenadas. A pontuação de cada tiro é feita da seguinte forma: para cada círculo em que o tiro estiver contido Juquinha recebe um ponto.
Considere por exemplo a figura abaixo. O tiro marcado com a letra A recebe zero pontos, pois não está contido por nenhum círculo. O tiro marcado com a letra B recebe um ponto, pois está contido por um círculo (o mais externo). O tiro marcado com a letra C recebe dois pontos, pois está contido por dois círculos (note que este caso mostra que tiros exatamente na borda de um círculo são considerados como contidos pelo círculo). Já o tiro marcado com a letra D recebe três pontos, pois está contido pelos três círculos. Considerando todos os pontos, a pontuação total de Juquinha é de 13 pontos.
Dados os raios de C círculos centrados na origem e as coordenadas dos T tiros realizados por Juquinha, escreva um programa que calcula o total de pontos que Juquinha obteve.
Entrada
A primeira linha da entrada contém dois inteiros positivos, C (1 ≤ C ≤ 105) e T (1 ≤ T ≤ 105), que representam, respectivamente, o número de círculos do alvo e o número de tiros.
Cada uma das C linhas seguintes contém um inteiro positivo. O i-ésimo inteiro Ri (1 ≤ Ri ≤ 106 para 1 ≤ i ≤ C) ,Ri > Ri-1 para 2 ≤ i ≤ C) representa o raio do i-ésimo círculo. Os raios Ri são fornecidos em ordem crescente.
Cada uma das T linhas seguintes contém um par X, Y (-105 ≤ X, Y ≤ 105) de inteiros, que representam as coordenadas de cada tiro.
Saída
Seu programa deve imprimir uma única linha, contendo apenas um inteiro, o total de pontos obtidos por Juquinha.
| Exemplos de Entrada | Exemplos de Saída |
|
3 10 1 2 5 0 0 -2 0 0 -2 3 -4 -4 -3 3 1 6 2 -1 2 -5 -2 1 -1 |
13 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
long long raios[100010];
int buscaBin(long long, long long);
int main (void)
{
unsigned i;
long long Px, Py;
long long qtsPontos, tmp;
long long qtsCirculos, qtsTiros;
scanf("%lld %lld", &qtsCirculos, &qtsTiros);
for (i = 1; i < = qtsCirculos; i++)
{
scanf("%lld", &tmp);
raios[i] = tmp * tmp;
}
qtsPontos = 0;
for (i = 1; i < = qtsTiros; i++)
{
scanf("%lld %lld", &Px, &Py);
qtsPontos += buscaBin((Px * Px + Py * Py), qtsCirculos);
}
printf("%lld\n", qtsPontos);
}
// Busca binária;
int buscaBin(long long distancia, long long qtsCirculos)
{
long long meio;
long long inicio = 1;
long long fim = qtsCirculos;
// Se a distância for maior do que o maior raio
// Então esse ponto está fora de todos os círculos;
if (distancia > raios[fim])
return 0;
while (inicio < fim)
{
meio = (inicio + fim) / 2;
if (raios[meio] >= distancia)
fim = meio;
else
inicio = meio + 1;
}
return qtsCirculos + 1 - fim;
}
Input
1
2
5
0 0
-2 0
0 -2
3 -4
-4 -3
3 1
6 2
-1 2
-5 -2
1 -1
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#define MAXN 100010
typedef long long ll;
ll n, m, resposta;
ll vetor[MAXN];
ll busca(ll valor) {
if (valor > vetor[n]) return 0;
ll ini = 1, fim = n, meio;
while (ini < fim) {
meio = (ini + fim) / 2;
if (vetor[meio] >= valor)
fim = meio;
else
ini = meio + 1;
}
return n + 1 - fim;
}
int main() {
scanf("%lld %lld", &n, &m);
for (ll i = 1; i < = n; i++) {
ll davez;
scanf("%lld", &vetor[i]);
vetor[i] *= vetor[i];
}
while (m--) {
ll x, y;
scanf("%lld %lld", &x, &y);
// printf("%lld %lld %lld\n",x,y,busca(x*x + y*y));
resposta += busca(x * x + y * y);
}
printf("%lld\n", resposta);
return 0;
}
Input
1
2
5
0 0
-2 0
0 -2
3 -4
-4 -3
3 1
6 2
-1 2
-5 -2
1 -1
Output