#P18488. Spacecraft
Spacecraft
Spacecraft
三维空间中有 颗位于不同坐标的星星,第 颗星星位于 。另有一艘以原点为球心、半径为 的球形飞船。
如果空间中的点 对每个 都满足下列条件,就称 是一个可爱点:从 能看到第 颗星星。也就是说,以 和 为端点的线段既不能穿过,也不能接触飞船的表面。
求所有可爱点构成的区域有多少个连通分量。严格地说,记所有可爱点组成的集合为 ;对 ,当且仅当存在一条完全位于 内、以 为端点的曲线时,定义 。请输出商集 的大小。可以证明,答案是一个非负整数。
给出 组测试用例,分别求解。
输入第一行是整数 。接下来给出 组测试用例;每组的格式为:
N R
x_1 y_1 z_1
...
x_N y_N z_N
所有输入值都是整数,并满足:
- ;
- ;
- 对每个 ,;
- 所有星星的坐标两两不同;
- 对每颗星星独立选择一条通过原点的直线 和实数 ,其中 ;将第 颗星星绕轴 旋转 弧度。**进行上述任意操作后,答案保持不变。**旋转后的坐标无须为整数。
每组测试用例输出一行,包含答案。
完整原样例输入:
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
第一组用例存在可爱点。例如 与给定四颗星星之间的线段都不穿过或接触飞船,因此是一个可爱点。 也是一个可爱点,且与前者属于同一连通分量。
第二组用例不存在可爱点。
下图展示视线锥与单位球的交圆及其所在平面,供理解空间关系。
