問題文
尺寸 有一个 L × L × L 的立方体形状的容器。玩一个游戏,尝试将球塞进这个容器中。
容器内的一点用笛卡尔坐标系表示,容器顶点的坐标之一是 (0, 0, 0) 和距离该顶点最远的顶点的坐标是 (L, L, L) 。
可以填充的球有 N 可用,球体 它被称为 1、球 2、…、球 N 。球体 i 的半径是 R_i 。
从这些球体中选择任意数量的球体,并将它们放置在容器中的任意整数坐标处(也就是说,放置它们以使球体的中心位于该整数坐标处)。
此时,球体可以漂浮在空中,但球体不能突出容器或相互重叠(球体接触容器或球体相互接触即可)。
将您的得分计算为以下球的位置的总和。
- 基礎点: 球 i 有基本点 P_i 被定义,并且球体 当 i 放入容器内时 P_i 可以获得积分。
- 奖励积分:最好靠近放置的球体对是 给出了 M 集。更具体地说,4 整数集 给出了 (A_i, B_i, C_i, D_i) 是 从 M 。其中每一个都是一个球体。 A_i 和球体 B_i 是中心之间的欧几里德距离。 C_i 当按如下方式放置在容器中时: D_i 表示可以获得积分。 (距离为 不禁止超过 C_i 的安排。 )
考虑一下球的放置位置,这将为您带来尽可能多的分数。无需寻找最优解。
制約
- L = 1000
- N = 1000
- M = 100000
- 1 ≦ R_i ≦ 200
- 1 ≦ P_i ≦ 80000
- 1 ≦ A_i < B_i ≦ N
- 1 ≦ C_i ≦ 600
- 1 ≦ D_i ≦ 80000
- 所有输入值都是整数。
入力
输入以以下格式给出。
L N M R_1 P_1 R_2 P_2 : R_N P_N A_1 B_1 C_1 D_1 A_2 B_2 C_2 D_2 : A_M B_M C_M D_M
出力
排列中的球体 i 的中心坐标是 按以下格式输出为 (X_i, Y_i, Z_i) 。然而,未放置在容器内的球体的中心坐标是 让它成为 (-1, -1, -1) 。
X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_N Y_N Z_N
在以下情况下,错误答案 已确定。
- 输出格式不正确(X_i, Y_i, Z_i 不是整数)。
- 球从容器中突出。换句话说,一个放置在容器内的球体 关于 i ,X_i - R_i, Y_i - R_i, Z_i - R_i 小于 0 或 大于X_i + R_i, Y_i + R_i, Z_i + R_i 小于 L 。
- 球体重叠。也就是说, 2 两个球体 对于 i, j (i < j) ,球体 i, j 中心之间的欧几里得距离为 小于 R_i + R_j 。
入力生成
无需阅读本节。
各球 i 的参数确定如下。
- 球 i 的半径 随机确定为小于或等于 R_i ,1 以上 200 的整数。
- 基礎点 P_i ,1 以上 \max(1,R_i^3/100) 的整数。
另外,i 物品奖励积分的参数确定如下。
- A_i, B_i ,1 以上 N 下面 2 随机确定为两个整数。但如果选择了相同的数值,则会进行重新抽签。之后,A_i > B_i 如果 交换 A_i 和 将其放在 B_i 的值。
- C_i ,R_{A_i} + R_{B_i} + 1 以上 R_{A_i} + R_{B_i} + 200 的整数。
- D_i ,1 以上 2R_{A_i}R_{B_i} 的整数。
採点
单个测试用例的分数计算为问题文本中所述的基分和奖励分之和。
测试用例是 50 给定一个案例,所有测试案例的分数总和就是该提交的分数。
另外,除了测试用例example_01之外, 1 输出也是 如果确定 错误答案 ,则除 example_01 之外的所有案例的得分 0 点。
示例代码 (C++)
您可以按原样提交此代码。