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

「CTS2019 | CTSC2019」无处安放

Cannot parse: undefinedms error parsing time

题目描述

这是一道提交答案题。

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

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

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

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

输入格式

输入文件 nowhere1.in\simnowhere10.in 已在试题目录下。
对于每组输入数据:
第一行两个整数 typetype, nn,分别表示安放方式与思绪的个数。
type=2type = 2,第二行两个整数 WW, HH,表示 RR 的边长。
接下来 nn 行每行两个整数 wiw_i, hih_i,表示第 ii 个思绪即 rir_i 的边长。
同一行中输入的整数均以一个空格分隔开。

输出格式

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

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

数据范围与提示

评分方式

评分准则 nowhere1.ans\simnowhere10.ans 已放在试题目录下。
每个测试点设置了 1010 个评分参数 a1,a2,,a10a_1, a_2,\cdots , a_10。若选手输出不合法,则得零分。否则,对于安放方式 11,令 valvalRR 的面积,若 valaival \le a_i,则你可获得 ii 分;对于安放方式 22,令 valval 为安放到 RR 中的思绪个数,若 valaival \ge a_i 则你可获得 ii 分。满足多个得分条件,测试点得分取最高者。