【2017】奶酪：判断Jerry能否通过球形空洞从奶酪下表面到达上表面

题目描述

现有一块大奶酪，它的高度为 h，长度和宽度可认为无限大，奶酪中间有许多半径相同的球形空洞。建立空间坐标系，奶酪下表面为 z = 0，上表面为 z = h。

奶酪下表面的小老鼠 Jerry 知道所有空洞的球心坐标：

• 若两个空洞相切或相交，Jerry 可以从一个空洞跑到另一个空洞；
• 若一个空洞与下表面相切或相交，Jerry 可以从下表面进入空洞；
• 若一个空洞与上表面相切或相交，Jerry 可以从空洞跑到上表面。

在不破坏奶酪的情况下，Jerry 能否利用已有空洞跑到奶酪上表面？

空间两点 $P_1(x_1,y_1,z_1)$、$P_2(x_2,y_2,z_2)$ 的距离公式如下： $$dist(P_1,P_2) = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 + (z_1-z_2)^2}$$

输入描述

每个输入文件包含多组数据：

1. 第一行是正整数 T，代表数据组数。
2. 每组数据格式如下：
   • 第一行三个正整数 n、h、r，分别代表空洞数量、奶酪高度、空洞半径，两个数之间用一个空格分隔。
   • 接下来 n 行，每行三个整数 x、y、z，代表空洞球心坐标 (x,y,z)，两个数之间用一个空格分隔。

输出描述

输出共 T 行，分别对应每组数据的答案：

• 若 Jerry 能从下表面跑到上表面，输出 Yes；
• 否则输出 No（均不包含引号）。

输入样例1

3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4

输出样例1

Yes
No
Yes

样例1解释

1. 第一组数据：第一个空洞(0,0,1)与下表面相切，第二个空洞(0,0,3)与上表面相切，两个空洞相切，连通上下表面，输出Yes。
2. 第二组数据：两个空洞既不相交也不相切，无法连通上下表面，输出No。
3. 第三组数据：两个空洞相交，且分别与上下表面相交/相切，连通上下表面，输出Yes。

数据规模与约定

• 对于20%的数据：n = 1，1 ≤ h,r ≤ 10000，坐标的绝对值不超过10000。
• 对于40%的数据：1 ≤ n ≤ 8，1 ≤ h,r ≤ 10000，坐标的绝对值不超过10000。
• 对于80%的数据：1 ≤ n ≤ 1000，1 ≤ h,r ≤ 10000，坐标的绝对值不超过10000。
• 对于100%的数据：1 ≤ n ≤ 1000，1 ≤ h,r ≤ 1000000000，T ≤ 20，坐标的绝对值不超过1000000000。