QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB

#23488. Papel mágico colorido

Statistics

Queremos pegar numa folha retangular de papel mágico colorido com linhas horizontais e verticais espaçadas de $1$ unidade

e cortá-la horizontal e verticalmente em peças retangulares mais pequenas.

Inicialmente é dada uma folha branca.

Depois, sempre que é dado um ponto, corta-se uma peça segundo as regras seguintes.

(1) Se o ponto pertencer a uma peça branca, corta-se pela linha horizontal que passa por esse ponto.

As duas peças resultantes tornam-se pretas.

(2) Se o ponto pertencer a uma peça preta, corta-se pela linha vertical que passa por esse ponto.

As duas peças resultantes tornam-se brancas.

Dados a largura e a altura do papel mágico branco e uma sequência ordenada de pontos no seu interior,

escreve um programa que, após todos os cortes segundo as regras acima, calcule a área da maior peça

e a área da menor peça.

Não existem dois pontos de entrada na mesma linha horizontal ou vertical.

Além disso, nenhum ponto de entrada está no contorno da folha original.

A largura e a altura do papel são inteiros positivos.

A posição de cada ponto de corte é dada por dois inteiros: a sua distância horizontal

e a sua distância vertical a partir do canto inferior esquerdo da folha original antes dos cortes.

Por exemplo, o ponto 1 nas figuras abaixo está em $(5,4)$.

Suponhamos que uma folha de largura $8$ e altura $7$ vai ser cortada nos pontos

$(5,4)$, $(2,3)$, $(3,1)$, $(7,6)$, $(6,2)$, dados por esta ordem.

Primeiro, o primeiro ponto corta a folha em duas peças pretas, como na figura 1.

problem_23488_cfd143e7033d82497b68c092e511c119.png

Figura 1

Depois, o segundo ponto divide a peça preta inferior da figura 1 em duas peças brancas, como na figura 2.

problem_23488_c853c5bf50df689b385dd80e4c731f46.png

Figura 2

Cortar em todos os pontos restantes da mesma forma produz a figura 3.

Neste caso, a maior peça tem área $21$ e a menor tem área $3$.

problem_23488_0366376e97a2bd2637b58388d5e30a2b.png

Figura 3

Entrada

A primeira linha contém dois inteiros positivos separados por um espaço: a largura e a altura do papel.

Ambas as dimensões são, no máximo, $40,000$.

A segunda linha contém um inteiro positivo $N$, o número de pontos de corte. Tem-se $N\le 30000$.

Da terceira à última linha são dados os pontos de corte por ordem, um por linha.

Cada posição é dada pela distância horizontal seguida da vertical, separadas por um espaço.

Saída

Na primeira linha escreve as áreas da maior e da menor peça, por esta ordem, separadas por um espaço.

Exemplos

Entrada 1

8 7 
5
5 4 
2 3 
3 1 
7 6 
6 2

Saída 1

21 3

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.