Meteoros

Em noites sem nuvens pode-se muitas vezes observar pontos brilhantes no céu que se deslocam com grande velocidade, e em poucos segundos desaparecem de vista: são as chamadas estrelas cadentes, ou meteoros. Meteoros são na verdade partículas de poeira de pequenas dimensões que, ao penetrar na atmosfera terrestre, queimam-se rapidamente (normalmente a uma altura entre 60 e 120 quilômetros). Se os meteoros são suficientemente grandes, podem não queimar-se completamente na atmosfera e dessa forma atingem a superfície terrestre: nesse caso são chamados de meteoritos.

Zé Felício é um fazendeiro que adora astronomia e descobriu um portal na Internet que fornece uma lista das posições onde caíram meteoritos. Com base nessa lista, e conhecendo a localização de sua fazenda, Zé Felício deseja saber quantos meteoritos caíram dentro de sua propriedade. Ele precisa de sua ajuda para escrever um programa de computador que faça essa verificação automaticamente.

Tarefa

São dados:

  • as coordenadas de um retângulo que delimita uma fazenda. O retângulo é determinado pelas coordenadas do seu canto superior esquerdo e pelas coordenadas do seu canto inferior direito.
  • uma lista de pontos no plano cartesiano, onde cada ponto corresponde à posição onde caiu um meteorito;

As linhas que delimitam a fazenda são paralelas aos eixos cartesianos. Sua tarefa é escrever um programa que determine quantos meteoritos caíram dentro da fazenda (incluindo meteoritos que caíram exatamente sobre as linhas que delimitam a fazenda).

Entrada

Seu programa deve ler vários conjuntos de testes. A primeira linha de um conjunto de testes é composta de quatro números inteiros X1, Y1, X2 e Y2, onde (X1, Y1) é a coordenada do canto superior esquerdo e (X2, Y2) é a coordenada do canto inferior direito do retângulo que delimita a fazenda. A segunda linha contém um inteiro, N, que indica o número de meteoritos. Seguem-se N linhas, cada uma contendo dois números inteiros X e Y, correspondendo às coordenadas de cada meteorito. O final da entrada é indicado por X1 = Y1 = X2 =Y2 = 0, ou seja, quando o usuário digitar a linha


0 0 0 0

significa que ele não quer verificar mais nenhuma fazenda e seu programa deve terminar.


OBSERVAÇÃO IMPORTANTE: não é permitido o uso de vetores no seu algoritmo!

Exemplo de Entrada

2 4 5 1
2
1 2
3 3
2 4 3 2
3
1 1
2 2
3 3
0 0 0 0

Note que, nessa esntrada, o usuário deseja verficar duas fazendas: a primeira formada pelo retângulo de coordenadas (2,4) e (5,1) e a segunda formada pelo retângulo de coordenadas (2,4) e (3,2). Na primeira fazenda, ele quer verificar se caíram dois meteoritos dados pelas coordenadas (1,2) e (3,3). Na segunda fazenda, ele quer verificar se caíram os três meteoritos dados pelas coordenadas (1,1), (2,2) e (3,3). Em seguida, o usuário não deseja fazer mais nenhum teste e, por isso, digita a linha 0 0 0 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A segunda linha deve conter o número de meteoritos que caíram dentro da fazenda. A terceira linha deve ser deixada em branco.

Exemplo de Saída

Teste 1
1

Teste 2
2

Esta saída corresponde ao exemplo de entrada dado acima. Note que, para cada uma das fazendas testadas (eram duas), deve-se imprimir na tela como resultado o número de meteoritos que caíram nesta fazenda.

Observações Importantes Para a Entrega

DATA DE ENTREGA: 22 de abril

FORMA DE ENTREGA: leve na aula o seu código escrito de próprio punho e com bastante comentários. Se você quiser, pode enviar o código digitado em C para o e-mail sheila.almeida@gmail.com. Coloque no assunto "meteoros - mc102". IMPORTANTE: entregar o código por e-mail não te isenta de levá-lo escrito a mão para a aula da quarta-feira (22/04), mas pode ajudar na sua nota.

Esse exercício vale nota e é individual!

A professora de teoria está a disposição de vocês para quaisquer dúvidas: mandem e-mails!


VOLTAR