← 返回题目列表

AtCoder · ttpc2023_d

D. 宇宙飞船

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

配点 : 100 点

問題文

3 维度空间中不同坐标处 N 星星在闪烁。 i 第一颗星星是一个点 存在于 P_i(x_i,y_i,z_i) 中。另外,半径 R 一艘球形飞船漂浮在原点周围。

空间中的点 p 是 在 好点 这意味着以下条件对于 意味着i = 1, 2, \dots, N 同时成立。 可以观测到

  • 点 p 减去 i 星。也就是说, 端点为 p 和 按字典顺序比较 P_i 的线段不会穿过航天器周围或内部。

查找存在好点的区域中连通分量的数量。换句话说,所有好点的集合是 L 当L 具有以下等价关系 求除以 \sim 时商集的大小。

  • p_1, p_2 \in L , 您可以获得p_1 和 按字典顺序比较 p_2 是终点 L 当且仅当上述曲线存在 p_1 \sim p_2 。

该值为 10^{18} 下面可以证明它是一个整数。

T 测试用例,因此请逐一回答。

制約

  • 所有输入均为整数
  • 1\le T\le 10
  • 1 \le N \le 500
  • 1 \le R \lt \sqrt{x_i^2+y_i^2+z_i^2} \le 10^3 \ (1\le i\le N)
  • (x_i,y_i,z_i) \neq (x_j,y_j,z_j)\ (1 \le i < j \le N)
  • 以下操作不会改变答案 对于
    • i=1,2,\dots ,N ,穿过原点的直线 l_i 和实数 \theta _i\ (|\theta _i|\le 10^{-6}) 独立选择。明星 i 位置 大约 l_i 的角度 移动到旋转了 \theta _i 的位置。

入力

输入是按以下格式从标准输入给出的。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

每个测试用例 \mathrm{case}_i 按以下格式给出。 如果

N R
x_1 y_1 z_1
\vdots
x_N y_N z_N

出力

打印答案。 来自


入力例 1

3
4 12
13 0 0
0 15 0
0 -15 0
0 0 15
6 100
0 0 101
0 0 -101
0 101 0
0 -101 0
101 0 0
-101 0 0
20 333
328 -160 -572
-165 417 -847
-319 -45 271
359 -467 -625
-355 -451 658
-280 -424 687
-65 -224 573
475 -371 373
-246 -54 -903
595 -196 -305
622 -570 -250
386 -541 -566
647 455 -424
734 117 -405
830 -10 -393
-334 137 154
74 459 -92
-651 -93 -131
879 148 45
-48 126 -660

出力例 1

1
0
3

1 最后一个测试用例有一个很好的观点。

  • 例如 第 (0,0,100) 是一个很好的观点。这一点并给出 4 连接任何点的线都没有穿过航天器的内部。

  • 其他 (21,0,0) 是一个很好的观点。

  • 这些 2 这些点属于同一连通分量。

2 在第三个测试用例中,没有什么好点。