← 返回题目列表

AtCoder · abc445_d

G. 重构巧克力

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

分数: 425 点

问题陈述

有 N 一块放在桌子上的巧克力块。 件 i\ (1 \leq i \leq N) 是一个矩形 h_i 块高大且 w_i 块宽。

已知这些碎片是通过以下程序获得的。

  • 首先拿着一块巧克力棒 H 块高大且 W 块宽。桌子上没有放置任何东西。
  • 重复以下操作 N-1 次。
    • 将当前手上的棋子分成两块。分割后的两块都必须是沿着块边界的矩形。
    • 将其中一块放在桌子上,并将另一块放在手中。
  • 最后,将手中的棋子放在桌子上。

找到一种方法来安排 N 切成矩形 H 块高大且 W 块宽满足以下条件。

  • 不同的部分不重叠。
  • 不得旋转棋子。也就是说,对于 h \neq w,一块 h 块高大且 w 块宽不能作为一块放置 w 块高大且 h 块宽。

约束

  • 1 \leq H \leq 10^9
  • 1 \leq W \leq 10^9
  • 2 \leq N \leq 2\times 10^5
  • 1 \leq h_i \leq H
  • 1 \leq w_i \leq W
  • 保证输入是通过问题陈述中描述的过程获得的。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

H W N
h_1 w_1
h_2 w_2
\vdots
h_N w_N

输出

在有效的排列中,让左上角的块 i\ (1 \leq i \leq N) 位于 x_i从顶部开始的第行和 y_i-整个矩形左侧的第列。输出格式如下:

x_1 y_1
x_2 y_2
\vdots
x_N y_N

如果有多个有效安排,则接受其中任何一个。


示例输入 1

4 6 6
2 2
1 4
3 1
1 2
3 1
4 2

示例输出 1

2 2
4 1
1 1
1 2
1 4
1 5

示例输出中的排列如下所示。


示例输入 2

100 100 20
72 7
4 74
17 67
20 67
96 3
1 95
5 81
87 3
3 87
16 67
95 8
100 2
92 1
3 98
92 5
87 3
1 98
19 67
11 74
87 1

示例输出 2

7 89
90 22
62 22
7 22
4 96
99 1
94 15
7 19
4 9
27 22
4 1
1 99
7 14
1 1
7 9
7 16
100 1
43 22
79 22
7 15