Prazo de entrega recomendado: 29/04/2021

Nesta tarefa, vamos exercitar o projeto de algoritmos e sua implementação em Python. Para esta atividade, será fundamental a utilização da estrutura de dados lista.

É muito comum que as pessoas que utilizam a internet sejam perturbadas por diversos anúncios, especialmente antes da popularização dos bloqueadores de anúncios, os chamados adblockers. No início da Web, os pop-ups eram o tormento dos internautas.

Além de inconvenientes, esses anúncios muitas vezes incluem rastreadores ou links maliciosos. Responsável e consciente que é, você ajudará a criar uma extensão de navegador que torna a navegação mais segura e agradável.

Atenção: no final da página são dadas algumas dicas de Python.

a) Prevenção de ameaças

Enquanto os pop-ups são coisa do passado, a tendência atual é colocar anúncios em vários retângulos sobrepostos sobre o conteúdo de uma página, cada um levando a um site diferente. Enquanto alguns levam a sites confiáveis, outros, nem tanto.

Sua tarefa é criar um programa classificar-clique.py que decide se, ao clicar em um anúncio, o usuário será redirecionado a um site seguro ou malicioso. A lista dos sites maliciosos mais comuns já é conhecida no momento da instalação da extensão, então basta descobrir qual retângulo será clicado.

Cada anúncio está associado a um endereço e corresponde a um retângulo representado pelas coordenadas do ponto inferior esquerdo $(x_0, y_0)$ e do ponto superior direito $(x_1, y_1)$. Todas as coordenadas são números inteiros não negativos. Um clique ativa um anúncio se estiver no interior ou na borda do retângulo e não houver nenhum outro retângulo encobrindo o ponto do clique.

Entrada

A entrada é composta de três partes:

a lista de sites maliciosos: a primeira linha contém inteiro $M$ e cada uma das $M$ seguintes tem o endereço de um site malicioso;
a lista de retângulos: uma linha contém um número $N$ e cada uma das $N$ linhas seguintes tem o formato x0 y0 x1 y1 endereço com as coordenadas de um retângulo e o endereço correspondente ao anúncio, começando do retângulo mais à frente para o mais atrás;
a lista de cliques: cada uma das linhas seguintes representa as coordenadas de um clique, com a exceção da última linha que tem coordenadas -1 -1 e representa o final da entrada.

3
trojan.com
malicious.com
virus.com
5
1 1 5 3 safe.com
2 4 6 6 benefical.com
3 0 4 9 virus.com
0 8 5 10 good.com
7 1 9 2 malicious.com
3 2
3 9
5 7
9 2
-1 -1

Saída

Para cada um dos cliques, deve haver uma linha correspondente classificando o objeto ativado. Se um anúncio for ativado, imprima seguro ou malicioso a depender da natureza deste. Se o clique não ativar algum anúncio deve ser impresso nenhum.

seguro
malicioso
nenhum
malicioso

b) Poluição visual

Ainda que alguns anúncios tenham conteúdo atrativo para nós, não gostaríamos que eles ocultassem o conteúdo de interesse, um player de vídeo, por exemplo. Um recurso ímpar da sua extensão é que ela será capaz de fechar anúncios até que o vídeo esteja completamente visível.

Sua tarefa é criar um programa fechar-anuncios.py que calcula o menor número de anúncios que precisamos fechar para ver o player completamente.

Entrada

A entrada é composta de duas partes:

a especificação do player: a primeira linha contém quatro inteiros no formato x0 y0 x1 y1 representado as coordenadas inferior esquerda e superior direita do player;
a lista de retângulos: uma linha contém um número $N$ e cada uma das $N$ linhas seguintes tem o formato x0 y0 x1 y1 com as coordenadas de um retângulo, começando do retângulo mais à frente para o mais atrás;

Saída

Deve ser impressa uma linha no formato Devem ser fechados X anúncios, na qual o valor X corresponde ao número mínimo de anúncios que devem ser fechados para que o player de vídeo esteja completamente visível. Anúncios que tocam alguma borda do player mas que não escondem parte do seu interior não devem ser contados.

Devem ser fechados 2 anúncios

c) Nível de perturbação (Opcional)

Mesmo que um site tenha um conteúdo incrível, uma má impressão faz com que o usuário prefira visitar a concorrência. Mais do que o número total de anúncios em uma página, o importante é o número de anúncios visíveis na sua primeira impressão. Esses dois números podem ser diferentes porque pode haver vários anúncios escondidos por detrás daqueles mais à frente.

Além de ajudar o usuário dos sites, sua extensão também ajuda os desenvolvedores web! Sua última tarefa é criar um programa anuncios-visiveis.py que mostra a quantidade de anúncios que podem ser vistos em uma primeira impressão.

Atenção: resolver esta questão não influencia na nota final da tarefa, porém vocês são encorajados a resolvê-la mesmo assim.

Entrada

A primeira linha da entrada contém um número $N$ e cada uma das $N$ linhas seguintes tem o formato x0 y0 x1 y1 com as coordenadas de um retângulo, começando do retângulo mais à frente para o mais atrás;

Saída

Deve haver uma linha no formato É possível ver X anúncios, na qual o valor X corresponde número de anúncios que podem ser vistos.

É possível ver 3 anúncios

Dicas

Você pode guardar um retângulo em uma lista com suas 4 coordenadas e guardar todos os retângulos em uma lista de listas.
Se uma linha da entrada contém apenas números inteiros você pode extrair dela uma lista utilizando o seguinte comando:
```
minhaLista = list(map(int, input().split()))
```
Você pode consultar o tamanho de uma lista em python utilizando a seguinte função:
```
tamanho = len(minhaLista)
```
Você pode excluir valores repetidos de uma lista em python utilizando o seguinte comando:
```
minhaLista2 = list(set(minhaLista))
```
Você pode ordenar uma lista em python utilizando o seguinte comando:
```
minhaLista.sort()
```

Correção

Esta tarefa será avaliada pelo corretor automático e por um monitor, mas sem apresentação do aluno. Para cada questão, há duas unidades teste consideradas: casos de teste de instâncias típicas e casos testes com casos de contorno (corner cases) e instâncias grandes. O conceito da tarefa será dado de acordo com as unidades resolvidas corretamente:

D se alguma instância de teste típica falhar;
C se algum instância de caso de contorno para a questão a falhar;
B se algum instância de caso de contorno para a questão b falhar;
A se todas as unidades passarem.

Lembre-se de que o monitor poderá confirmar ou revisar a nota atribuída automaticamente. Atente-se para o relatório de correção da sua tarefa! Procure ler e entender o feedback dado pelo monitor e procure corrigir os problemas identificados nesta e em tarefas futuras. Se tiver dúvidas, não deixe de procurar atendimento.

A pasta da tarefa no seu repositório vem inicialmente com um arquivo nao_corrigir.txt que serve para indicar que você ainda está trabalhando nesta tarefa. Você pode realizar quantos pushes quanto forem necessários. O monitor só irá corrigir sua tarefa quando esse arquivo for removido do repositório.