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 翻译