#P5402. [CTS2019] 无处安放

    ID: 5130 远端评测题 2000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2019WC/CTSC/集训队提交答案Special Judge

[CTS2019] 无处安放

题目背景

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

题目描述

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

你有两种安放方式:

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

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

输入格式

第一行两个整数 type,ntype, n,分别表示安放方式与思绪的个数。

type=2type = 2,第二行两个整数 W,HW, H,表示 RR 的边长。

接下来 nn 行每行两个整数 wi,hiw_i, h_i,表示第 ii 个思绪即 rir_i 的边长。

同一行中输入的整数均以一个空格分隔开。

输出格式

为了方便,若 RR 的边长为 W,HW, H,我们将安放方案视作一个 (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, dirid_{ir_i}。若 diri=0d_{ir_i} = 0,则 rir_i 放置在 (xi,yi)(xi+wi,yi+hi)(x_i, y_i)\sim(x_i + w_i, y_i + h_i) 的矩形范围内;若 diri=1d_{ir_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, d_{ir_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

提示

评分方式

每个测试点设置了 1010 个评分参数 a1,a2,...,a10a_1, a_2, ..., a_{10}。若选手输出不合法,则得零分。

否则,对于安放方式 11,令 valvalRR 的面积,若 valaival \leq a_i,则你可获得 ii 分;对于安放方式 22,令 valval 为安放到 RR 中的思绪个数,若 valaival \geq a_i 则你可获得 ii 分。满足多个得分条件,测试点得分取最高者。