QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB

#23488. Magiczny kolorowy papier

Statistics

Chcemy wziąć prostokątny arkusz magicznego kolorowego papieru z poziomymi i pionowymi liniami w odstępach $1$

i pociąć go poziomo i pionowo na mniejsze prostokątne kawałki.

Początkowo dany jest jeden biały arkusz.

Następnie, po podaniu każdego punktu, tniemy kawałek według poniższych zasad.

(1) Jeśli punkt leży w białym kawałku, tniemy wzdłuż poziomej linii przechodzącej przez ten punkt.

Oba powstałe kawałki stają się czarne.

(2) Jeśli punkt leży w czarnym kawałku, tniemy wzdłuż pionowej linii przechodzącej przez ten punkt.

Oba powstałe kawałki stają się białe.

Mając szerokość i wysokość białego magicznego papieru oraz uporządkowany ciąg punktów w jego wnętrzu,

napisz program, który po wykonaniu wszystkich cięć zgodnie z powyższymi zasadami obliczy pole największego kawałka

oraz pole najmniejszego kawałka.

Żadne dwa punkty wejściowe nie leżą na tej samej poziomej ani pionowej linii.

Ponadto żaden punkt wejściowy nie leży na brzegu początkowego arkusza.

Szerokość i wysokość papieru są dodatnimi liczbami całkowitymi.

Pozycja każdego punktu cięcia jest podana jako dwie liczby całkowite: jego odległość pozioma

i pionowa od lewego dolnego rogu początkowego, niepociętego arkusza.

Na przykład punkt 1 na poniższych rysunkach ma pozycję $(5,4)$.

Załóżmy, że arkusz o szerokości $8$ i wysokości $7$ ma być cięty w punktach

$(5,4)$, $(2,3)$, $(3,1)$, $(7,6)$, $(6,2)$, podanych w tej kolejności.

Najpierw pierwszy punkt dzieli arkusz na dwa czarne kawałki, jak na rysunku 1.

problem_23488_cfd143e7033d82497b68c092e511c119.png

Rysunek 1

Następnie drugi punkt dzieli dolny czarny kawałek z rysunku 1 na dwa białe kawałki, jak na rysunku 2.

problem_23488_c853c5bf50df689b385dd80e4c731f46.png

Rysunek 2

Cięcia we wszystkich pozostałych punktach w ten sam sposób dają rysunek 3.

W tym przypadku największy kawałek ma pole $21$, a najmniejszy pole $3$.

problem_23488_0366376e97a2bd2637b58388d5e30a2b.png

Rysunek 3

Wejście

Pierwszy wiersz zawiera dwie dodatnie liczby całkowite oddzielone spacją: szerokość i wysokość papieru.

Oba wymiary wynoszą co najwyżej $40,000$.

Drugi wiersz zawiera dodatnią liczbę całkowitą $N$, liczbę punktów cięcia. Zachodzi $N\le 30000$.

Od trzeciego do ostatniego wiersza podane są kolejno punkty cięcia, po jednym na wiersz.

Każda pozycja jest podana jako odległość pozioma, a następnie pionowa, oddzielone spacją.

Wyjście

W pierwszym wierszu wypisz pola największego i najmniejszego kawałka, w tej kolejności, oddzielone spacją.

Przykład

Wejście 1

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

Wyjście 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.