AT_ttpc2023_d.Spacecraft

在三维空间中，有 $N$ 颗星星分布在各不相同的坐标上。第 $i$ 颗星星位于点 $P_i(x_i, y_i, z_i)$。此外，以原点为中心、半径为 $R$ 的球形宇宙飞船悬浮在空间中。

空间中的某个点 $p$ 被称为美丽点，当且仅当对于 $i=1, 2, \dots, N$，同时满足以下条件：

• 能从点 $p$ 观测到第 $i$ 颗星星。即，$p$ 与 $P_i$ 之间的线段不会穿过宇宙飞船的球体及其内部。

请你计算美丽点所在区域的连通分量的个数。换句话说，设所有美丽点的集合为 $L$，请按如下等价关系 $\sim$ 将 $L$ 划分，问商集合的大小是多少。

• 对于 $p_1, p_2 \in L$，若存在 $L$ 上的一条曲线以 $p_1$、$p_2$ 为端点，则 $p_1 \sim p_2$；反之亦然。

此外，可以证明这个值不会超过 $10^{18}$。

给定 $T$ 个测试用例，请分别作答。

输入通过标准输入给出，格式如下：

$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

在第 $1$ 个测试用例中，存在美丽点。

• 例如 $(0,0,100)$ 就是一个美丽点。将该点与给定的 $4$ 个点各自连成的线段都不会穿过宇宙飞船球体的内部。
• 另一个例子是 $(21,0,0)$，它同样是美丽点。
• 这两个点属于同一个连通分量。

在第 $2$ 个测试用例中，不存在美丽点。

数据范围

• 所有输入都是整数。
• $1 \le T \le 10$
• $1 \le N \le 500$
• $1 \le R < \sqrt{x_i^2 + y_i^2 + z_i^2} \le 10^3\quad (1 \le i \le N)$
• 对于所有 $i < j$，有 $(x_i, y_i, z_i) \neq (x_j, y_j, z_j)$
• 对于以下的操作，答案不会变化：
  • 对于 $i = 1, 2, \dots, N$，任选一条经过原点的直线 $l_i$ 和一个实数 $\theta_i\ (|\theta_i| \le 10^{-6})$，将星星 $i$ 的位置绕 $l_i$ 旋转 $\theta_i$ 角度。

由 ChatGPT 5 翻译