#P18488. Spacecraft

Spacecraft

Spacecraft

三维空间中有 NN 颗位于不同坐标的星星,第 ii 颗星星位于 Pi=(xi,yi,zi)P_i=(x_i,y_i,z_i)。另有一艘以原点为球心、半径为 RR 的球形飞船。

如果空间中的点 pp 对每个 i=1,2,…,Ni=1,2,\ldots,N 都满足下列条件,就称 pp 是一个可爱点:从 pp 能看到第 ii 颗星星。也就是说,以 pp 和 PiP_i 为端点的线段既不能穿过,也不能接触飞船的表面。

求所有可爱点构成的区域有多少个连通分量。严格地说,记所有可爱点组成的集合为 LL;对 p1,p2∈Lp_1,p_2\in L,当且仅当存在一条完全位于 LL 内、以 p1,p2p_1,p_2 为端点的曲线时,定义 p1∼p2p_1\sim p_2。请输出商集 L/∼L/{\sim} 的大小。可以证明,答案是一个非负整数。

给出 TT 组测试用例,分别求解。

输入第一行是整数 TT。接下来给出 TT 组测试用例;每组的格式为:

N R
x_1 y_1 z_1
...
x_N y_N z_N

所有输入值都是整数,并满足:

  • 1≤T≤101\le T\le10;
  • 1≤N≤5001\le N\le500;
  • 对每个 ii,1≤R<xi2+yi2+zi2≤1031\le R<\sqrt{x_i^2+y_i^2+z_i^2}\le10^3;
  • 所有星星的坐标两两不同;
  • 对每颗星星独立选择一条通过原点的直线 ℓi\ell_i 和实数 θi\theta_i,其中 ∣θi∣≤10−6|\theta_i|\le10^{-6};将第 ii 颗星星绕轴 ℓi\ell_i 旋转 θi\theta_i 弧度。**进行上述任意操作后,答案保持不变。**旋转后的坐标无须为整数。

每组测试用例输出一行,包含答案。

完整原样例输入:

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
0
3

第一组用例存在可爱点。例如 (0,0,100)(0,0,100) 与给定四颗星星之间的线段都不穿过或接触飞船,因此是一个可爱点。(21,0,0)(21,0,0) 也是一个可爱点,且与前者属于同一连通分量。

第二组用例不存在可爱点。

下图展示视线锥与单位球的交圆及其所在平面,供理解空间关系。

球面交圆及平面