← 返回题目列表

Codeforces · 31/D

D. 巧克力

中文机器翻译题面 查看原题

Bob 有一块尺寸为 W × H 的矩形巧克力棒。他引入了笛卡尔坐标系,使得点 (0, 0) 对应于巧克力棒的左下角,点 (W, H) 对应于右上角。鲍勃决定通过打破它来将其分成几块。每个断点都是与其中一个坐标轴平行的线段,它连接钢筋的边缘。更正式地说,每个中断都沿着线 x = xc 或 y = yc,其中 xc 和 yc 是整数。它应该将栏的一部分分成两个非空部分。 Bob 将某个部分分成两部分后,他将生成的部分单独且彼此独立地分解。他也没有移动酒吧的各个部分。鲍勃做了 n 次中断,并以任意顺序将它们记在笔记本上。最后他得到了n+1个零件。现在他想计算它们的面积。鲍勃很懒,所以他让你做这个任务。

输入

第一行包含 3 个整数 W、H 和 n (1 ≤ W, H, n ≤ 100) — 条形宽度、条形高度和中断数量。以下 n 行中的每一行包含四个整数 xi, 1, yi, 1, xi, 2, yi, 2 — 第 i 个断点的端点坐标 (0 ≤ xi, 1 ≤ xi, 2 ≤ W, 0 ≤ yi, 1 ≤ yi, 2 ≤ H, 或 xi, 1 = xi, 2, 或 yi, 1 = yi, 2)。中断以任意顺序给出。

保证一组中断是正确的,即给定中断存在某种顺序,每个下一个中断将条形的一部分精确地分成两个非空部分。

输出

输出 n + 1 个数字 — 按升序排列的结果部分的面积。

示例

输入 #1

2 2 2
1 0 1 2
0 1 1 1

输出 #1

1 1 2

输入 #2

2 2 3
1 0 1 2
0 1 1 1
1 1 2 1

输出 #2

1 1 1 1

输入 #3

2 4 2
0 1 2 1
0 3 2 3

输出 #3

2 2 4