Problema A - Futebol
O Futebol Clube da Trafaria (FCT) vai construir o seu centro de estágios num terreno rectangular cedido pela autarquia.
Infelizmente, nesse terreno existe um bosque e, para podermos lá meter um campo de futebol, vai ser preciso cortar algumas
árvores. O campo de futebol também é rectangular e os lados devem ser paralelos aos lados do terreno. Devido a requisitos
ambientais inultrapassáveis, o FCT deve realizar este seu projecto abatendo o menor número de árvores que for possível.
Curiosamente, o bosque foi plantado “matematicamente”, de tal modo que se dividirmos o bosque em quadrículas de lado unitário,
em cada uma delas ou existe uma única árvore ou não existe árvore nenhuma (e nenhuma árvore está plantada sobre a fronteira das
quadrículas). A sua tarefa é calcular o local em que deve ser implantado o campo de futebol de maneira a minimizar o número de
árvores a abater.
O Problema
Escreva um programa para resolver o problema do centro de estágios.
Input
A primeira linha do input tem dois números inteiros positivos, C e L, representando o comprimento e a
largura do rectângulo do campo de futebol. A segunda linha tem também dois números inteiros positivos, HF e VF,
representando as dimensões na horizontal e na vertical do terreno (0 < HF, VF ≤ 1000).
Por definição, o comprimento C é a medida do lado horizontal do rectângulo do campo e a largura L é a medida
do lado vertical. A terceira linha tem um número inteiro N (0 ≤ N), o número de árvores existentes no bosque.
Cada uma das N linhas seguintes tem dois números inteiros, sem duplicados (isto é, todos os pares de números são diferentes),
representando as coordenadas do canto inferior esquerdo das quadrículas nas quais existe cada uma das N árvores.
Recorde que não há árvores em todas as quadrículas, mas todas as árvores estão dentro do terreno. A quadrícula no canto
inferior esquerdo do terreno tem coordenadas (0, 0). (Veja a ilustração mais abaixo.)
Os valores do C e L são tais que o problema tem sempre solução.
Output
O output tem duas linhas. Na primeira linha vêm dois números: as coordenadas do canto inferior esquerdo do campo de futebol.
Na segunda linha vem um número inteiro: o número de árvores a abater. Se houver vários rectângulos que minimizem o
número de árvores a abater o seu programa deve escolher aquele cuja coordenada x seja menor. Se houver vários com a mesma
coordenada x, deve escolher aquele cuja coordenada y seja menor.
Exemplo de Input
3 2
8 5
19
0 2
0 4
1 0
1 1
1 3
2 2
2 3
3 1
4 1
4 3
4 4
5 0
5 4
6 1
6 2
7 0
7 2
7 3
7 4
Exemplo de Output
3 2
1
Ilustração
O seguinte desenho ilustra a situação descrita no caso usado no exemplo. Cada ‘a’ representa uma árvore.
A cinzento está marcado o local onde deve ser construído o campo de futebol:
|
4
|
a
|
|
|
|
a
|
a
|
|
a
|
|
3
|
|
a
|
a
|
|
a
|
|
|
a
|
|
2
|
a
|
|
a
|
|
|
|
a
|
a
|
|
1
|
|
a
|
|
a
|
a
|
|
a
|
|
|
0
|
|
a
|
|
|
|
a
|
|
a
|
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
Final das Olimpíadas Nacionais de Informática 2005
(20 de Maio de 2005)