← 返回题目列表

AtCoder · icpc2014summer_day4_c

C. 魔法子弹

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

问题陈述

公元20XX年,校际魔法竞技大会正在举行。大会终于只剩下最后的竞技。你是那场竞技的参赛选手之一。

你出场的竞技项目,是比拼在空间内破坏所有放置的蓝色物体所需的时间。选手被允许携带用于竞技的枪。空间内摆放着多个蓝色物体和相同数量的红色物体,以及多个障碍物。蓝色物体和红色物体一一对应,必须从放置红色物体的坐标向蓝色物体射击,才能破坏蓝色物体。空间内摆放的障碍物是球状的,组成略有不同,但如果是普通子弹,碰到障碍物时子弹会停在原地。

用于竞技的子弹是称为魔法子弹的特殊子弹。这种子弹可以储存魔力,并在子弹接触障碍物时自动消耗魔力。由于障碍物的组成不同,为了路线障碍物所需要的魔法以及为发动魔法而消耗的魔力量也不同。因此,即使针对某一障碍物的魔法已经发动,为了路线其他障碍物,仍需要重新发动不同的魔法。此外,如果子弹同时接触到多个障碍物,魔法将同时发动。子弹中储存的魔力量在每次魔法发动时都会减少。

障碍物的位置和大小,以及争端魔法的发动所需的魔力量已经公开,而红色物体和蓝色物体的位置尚未公开。然而,从过去相同竞技的情报中,可以在一定程度上预测物体的位置。由于将魔力注入弹中会非常消耗体力,你希望尽可能节省魔力。因此,假设红色物体及其对应的蓝色物体的位置,求出此时弹中应注入的最小魔力量,也就是在弹到达蓝色物体时弹中剩余魔力为0所需的魔力量。


输入

输入全为整数,每个数字由一个空格分隔。

$N\ Q$
$x_1\ y_1\ z_1\ r_1\ l_1$
:
:
$x_N\ y_N\ z_N\ r_N\ l_N$
$sx_1\ sy_1\ sz_1\ dx_1\ dy_1\ dz_1$
:
:
$sx_Q\ sy_Q\ sz_Q\ dx_Q\ dy_Q\ dz_Q$
  • $N$ 是障碍物的数量,$Q$ 是假设的蓝色物体和红色物体坐标对的数量。
  • $x_i, y_i, z_i$ 分别表示第 $i$ 个障碍物中心的x坐标、y坐标、z坐标。
  • $r_i$ 是第 $i$ 个障碍物的半径。
  • $l_i $是魔法穿透第$i$个障碍物所消耗的魔法力量。
  • $sx_j、sy_j、sz_j$ 分别是表示第 $j$ 个假设中红色物体位置的 x、y 和 z 坐标。
  • $dx_j、dy_j、dz_j$ 分别是表示第 $j$ 个假设中蓝色物体位置的 x、y 和 z 坐标。

约束

  • $0 \leq N \leq 50$
  • $1 \leq Q \leq 50$
  • $-500 \leq x_i,y_i,z_i \leq 500$
  • $1 \leq r_i \leq 1{,}000$
  • $1 \leq l_i \leq 10^{16}$
  • $-500 \leq sx_j,sy_j,sz_j \leq 500$
  • $-500 \leq dx_j,dy_j,dz_j \leq 500$
  • 障碍物未嵌入其他障碍物中。
  • 对象坐标位于障碍物内部,而不是表面上
  • 在每个假设中,红色对象和蓝色对象的坐标都不匹配。

输出

假设一对红色物体和对应的蓝色物体的位置,并假设空间中只有障碍物和一对红蓝物体,将子弹中应该储存的魔力值排成一行输出。假设子弹从红色物体的位置直线飞行到蓝色物体的位置,由于子弹的尺寸很小,所以将其视为一个点。


示例输入 1

5 1
0 10 0 5 2
0 20 0 5 12
0 30 0 5 22
0 40 0 5 32
0 50 0 5 42
0 0 0 0 60 0

样本输入 1 的输出

110

示例输入 2

1 1
10 5 0 5 9
0 0 0 9 12 0

样本输入 2 的输出

9

示例输入 3

5 5
-38 -71 -293 75 1
-158 -38 -405 66 1
-236 -303 157 266 1
316 26 411 190 1
207 -312 -27 196 1
-50 292 -375 -401 389 -389
460 278 409 -329 -303 411
215 -220 -200 309 -474 300
261 -494 -87 -300 123 -463
386 378 486 -443 -64 299

样本输入 3 的输出

0
2
1
3
0