QOJ.ac

QOJ

Límite de tiempo: 1 s Límite de memoria: 128 MB

#23488. 魔法彩纸

Estadísticas

有一张长方形魔法彩纸,上面画有间距为 $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.