QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB

#23488. 魔法色紙

Statistics

有一張長方形魔法色紙,上面畫有間距為 $1$ 的水平線和垂直線,

現在要沿水平方向和垂直方向切割,將它分成小長方形紙片。

最初給定一張白色色紙。

之後每給出一個點,就按照以下規則切割紙片。

(1) 如果給定點位於白色紙片中,就沿經過該點的水平線切割。

切出的兩張紙片都會變成黑色。

(2) 如果給定點位於黑色紙片中,就沿經過該點的垂直線切割。

切出的兩張紙片都會變成白色。

給定白色魔法色紙的寬和高,以及紙內依序給出的若干個點,

請編寫程式,在按上述規則完成所有切割後,求出所得紙片中面積最大的紙片的面積,

以及面積最小的紙片的面積。

輸入的任意兩個點都不會位於同一條水平線或同一條垂直線上。

此外,輸入的點也不會位於最初那張色紙的邊界上。

色紙的寬和高均為正整數。

用於切割的每個點的位置由兩個整數給出,分別表示它到切割前色紙左下角的水平距離

和垂直距離。

例如,下圖中點 1 的位置為 $(5,4)$。

假設寬為 $8$、高為 $7$ 的色紙,其切割點位置

按 $(5,4)$、$(2,3)$、$(3,1)$、$(7,6)$、$(6,2)$ 的順序給出。

首先,第一個點將色紙切成兩張黑色紙片,如圖 1 所示。

problem_23488_cfd143e7033d82497b68c092e511c119.png

圖 1

接著,第二個點將圖 1 中下方的黑色紙片分成兩張白色紙片,如圖 2 所示。

problem_23488_c853c5bf50df689b385dd80e4c731f46.png

圖 2

對其餘各點也用同樣的方法切割色紙,就得到圖 3。

此時,最大紙片的面積為 $21$,最小紙片的面積為 $3$。

problem_23488_0366376e97a2bd2637b58388d5e30a2b.png

圖 3

輸入格式

第一行給出兩個以空格分隔的正整數,分別表示色紙的寬和高。

寬和高都不超過 $40,000$。

第二行給出正整數 $N$,表示切割點的數量,滿足 $N\le 30000$。

從第三行到最後一行,依序給出切割點的位置,每行一個。

每個點的位置先給出水平距離,再給出垂直距離,中間用空格分隔。

輸出格式

第一行依次輸出最大紙片的面積和最小紙片的面積,中間用空格分隔。

範例

輸入格式 1

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

輸出格式 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.