XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: viagem.x, onde x deve ser c, cpp, java, js ou py

Viagem Espacial

A empresa de jogos Sonyc está desenvolvendo um novo jogo de naves espaciais, chamado Space Traveller (Viajante Espacial). O objetivo do jogo é viajar entre dois pontos sem colidir com nenhum asteróide no caminho.

Para o protótipo, você foi contratado para implementar o programa responsável por verificar se um tiro disparado pela nave atingiu um determinado asteróide. Nessa primeira versão, os tiros disparados pela nave são projeções num plano 2D, formando uma linha reta infinita, e asteróides são circunferências perfeitas. Para que um tiro efetivamente destrua qualquer asteróide, ele deve tangenciar a circunferência que define o asteróide.

Dada uma sequências de tiros realizados pela nave e a localização de um asteróide, você deve dizer quantos tiros acertaram o asteróide.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém quatro números inteiros N , XC, YC e R (1 ≤ N ≤ 1.000,0 ≤ XC ≤ 1.000, 0 ≤ YC ≤ 1.000, 1 ≤ R ≤ 1.000) indicando, respectivamente, o número de tiros, as duas coordenadas no plano do centro do asteróide (XC, YC), e o raio do asteróide.

Em seguida haverá N linhas, uma para cada tiro. Cada linha terá 4 inteiros X1, Y1, X2, Y2(0 ≤ X1, X2, Y1, Y2 ≤ 1.000), representando duas coordenadas de pontos distintos da reta formada pela projeção do tiro.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo um inteiro, indicando quantos tiros atigiram o asteróide.

Informações sobre a pontuação

  • Em um conjunto de casos de teste que totaliza 30 pontos, N ≤ 10 e X1, Y1, X2, Y2, Xc, Yc, R ≤ 20
  • Em um conjunto de casos de teste que totaliza 55 pontos, N ≤ 100 e X1, Y1, X2, Y2, Xc, Yc, R ≤ 100

Exemplos

Exemplo de entrada
2 10 10 5
10 1 10 3
4 11 4 10
			
Exemplo de Saída
1		
			

Exemplo de entrada
2 5 5 1
0 0 0 1
0 0 1 0
			
Exemplo de Saída
0		
			

Exemplo de entrada
3 6 4 2
1 4 2 4
1 5 6 4
0 0 6 1
			
Exemplo de Saída
2		
			
Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação