← 返回题目列表

AtCoder · caddi2019_a

A. 球馅

中文机器翻译题面 查看原题

問題文

尺寸 有一个 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++)

示例代码

您可以按原样提交此代码。