#3121. 「CTS2019 | CTSC2019」无处安放

题目类型:答案提交 评测方式:Special Judge
上传者: 匿名

题目描述

这是一道提交答案题。

寂寥深夜,朦朦胧胧的月光为一切都笼上一层轻纱,你漫步在幽径,时而低头沉吟,时而凝望星空,只独孤与彷徨作伴,哪怕只言片语却也无人倾诉,万千思绪伴着你炽热的心,随风而动,无处安放……

你整理出了 n 条思绪,它们在你的心中是一个个矩形 r_i ,你想要在心中用一个大矩形 R 安放它们,也就是将 r_i 放置在 R 内部。为了保护这些思绪,它们安放的位置不能与其他思绪有重合部分,并且四条边要平行或垂直于 R 的边。两个思绪有重合部分,指它们安放位置的重合面积大于零。
你有两种安放方式:

  1. n 条思绪全部安放进 R 中,希望令 R 的面积尽量小。
  2. 固定 R 的大小,希望将尽量多的思绪安放进 R 中。

现在我已知晓你整理好的思绪,为你选择了安放的方式,我想知道你心中最好的安放方案,请你告诉我。

输入格式

输入文件 nowhere1.in \sim nowhere10.in 已在试题目录下。
对于每组输入数据:
第一行两个整数 type , n ,分别表示安放方式与思绪的个数。
type = 2 ,第二行两个整数 W , H ,表示 R 的边长。
接下来 n 行每行两个整数 w_i , h_i ,表示第 i 个思绪即 r_i 的边长。
同一行中输入的整数均以一个空格分隔开。

输出格式

将输入文件对应的答案,输出到 nowhere1.out \sim nowhere10.out 中。
为了方便,若 R 的边长为 W , H ,我们将安放方案视作一个 (0, 0) \sim (W, H) 的直角坐标系。注意对于 type = 2 的测试点,你应按输入,将其视作 (0, 0) \sim (W, H) 的坐标系,而不是 (0, 0) \sim (H, W) 的坐标系。
输出共有 n 行,每行一或四个整数,描述第 i 个思绪即 r_i 的放置方案。
每行第一个整数 c_i ,其中 c_i = 1 表示 r_i 被安放在 R 中; c_i = 0 表示 r_i 未被安放在 R 中。
c_i = 1 , 则该行接下来应输出三个整数 x_i , y_i , dir_i 。若 dir_i = 0 ,则 r_i 放置在 (x_i, y_i) \sim (x_i +w_i, y_i +h_i) 的矩形范围内;若 dir_i = 1 ,则 r_i 放置在 (x_i, y_i) \sim (x_i +h_i, y_i +w_i) 的矩形范围内。
请注意确保你的输出格式正确,且 c_i, dir_i \in \{0, 1\} 。对于 type = 1 的测试点,所有 c_i 均应为 1
同一行中输出的整数应以一个空格分隔开。

样例

样例 1 输入

1 3
1 1
1 1
2 1

样例 1 输出

1 0 0 0
1 0 1 0
1 1 0 1

样例 2 输入

2 4
2 2
1 1
1 1
2 1
2 1

样例 2 输出

1 0 0 0
1 0 1 0
1 1 0 1
0

数据范围与提示

评分方式

评分准则 nowhere1.ans \sim nowhere10.ans 已放在试题目录下。
每个测试点设置了 10 个评分参数 a_1, a_2,\cdots , a_10 。若选手输出不合法,则得零分。否则,对于安放方式 1 ,令 val R 的面积,若 val \le a_i ,则你可获得 i 分;对于安放方式 2 ,令 val 为安放到 R 中的思绪个数,若 val \ge a_i 则你可获得 i 分。满足多个得分条件,测试点得分取最高者。

编辑器加载中 …