loj#P3121. 「CTS2019 | CTSC2019」无处安放
「CTS2019 | CTSC2019」无处安放
Cannot parse: undefinedms error parsing time
题目描述
这是一道提交答案题。
寂寥深夜,朦朦胧胧的月光为一切都笼上一层轻纱,你漫步在幽径,时而低头沉吟,时而凝望星空,只独孤与彷徨作伴,哪怕只言片语却也无人倾诉,万千思绪伴着你炽热的心,随风而动,无处安放……
你整理出了 条思绪,它们在你的心中是一个个矩形 ,你想要在心中用一个大矩形 安放它们,也就是将 放置在 内部。为了保护这些思绪,它们安放的位置不能与其他思绪有重合部分,并且四条边要平行或垂直于 的边。两个思绪有重合部分,指它们安放位置的重合面积大于零。
你有两种安放方式:
- 将 条思绪全部安放进 中,希望令 的面积尽量小。
- 固定 的大小,希望将尽量多的思绪安放进 中。
现在我已知晓你整理好的思绪,为你选择了安放的方式,我想知道你心中最好的安放方案,请你告诉我。
输入格式
输入文件 nowhere1.in
nowhere10.in
已在试题目录下。
对于每组输入数据:
第一行两个整数 , ,分别表示安放方式与思绪的个数。
若 ,第二行两个整数 , ,表示 的边长。
接下来 行每行两个整数 , ,表示第 个思绪即 的边长。
同一行中输入的整数均以一个空格分隔开。
输出格式
将输入文件对应的答案,输出到 nowhere1.out
nowhere10.out
中。
为了方便,若 的边长为 , ,我们将安放方案视作一个 的直角坐标系。注意对于 的测试点,你应按输入,将其视作 的坐标系,而不是 的坐标系。
输出共有 行,每行一或四个整数,描述第 个思绪即 的放置方案。
每行第一个整数 ,其中 表示 被安放在 中; 表示 未被安放在 中。
若 , 则该行接下来应输出三个整数 , , 。若 ,则 放置在 的矩形范围内;若 ,则 放置在 的矩形范围内。
请注意确保你的输出格式正确,且 。对于 的测试点,所有 均应为 。
同一行中输出的整数应以一个空格分隔开。
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
nowhere10.ans
已放在试题目录下。
每个测试点设置了 个评分参数 。若选手输出不合法,则得零分。否则,对于安放方式 ,令 为 的面积,若 ,则你可获得 分;对于安放方式 ,令 为安放到 中的思绪个数,若 则你可获得 分。满足多个得分条件,测试点得分取最高者。