AcWing 528. 奶酪
原题链接
简单
作者:
soulmate.
,
2024-04-07 00:24:16
,
所有人可见
,
阅读 1
def find(x): # 查找x的祖宗
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(x, y): # 将x的祖宗指向y
if find(x) != find(y):
p[find(x)] = find(y)
T = int(input()) # 数据组数
for i in range(1, T + 1): # 输入数值
lis = [[0, 0, 0]]
n, h, r = map(int, input().split())
for j in range(n):
lis.append(list(map(int, input().split()))) # 输入三个数,x,y,z
p = [0] * 1086
for i in range(0, n + 2): # 从0到n + 2是因为包括上下表面
p[i] = i # 初始化并查数组
# 判断是否与上下表面存在关系
for i in range(1, n + 1):
if abs(lis[i][2] - 0) <= r:
union(i, 0)
if abs(lis[i][2] - h) <= r:
union(i, n + 1)
# 判断球心之间是否存在关系
for i in range(1, n + 1): # 多加思考,这里优化了步骤,避免重复计算
for j in range(1, i):
x = lis[i][0] - lis[j][0]
y = lis[i][1] - lis[j][1]
z = lis[i][2] - lis[j][2]
if x ** 2 + y ** 2 + z ** 2 <= 4 * r ** 2:
union(i, j)
# 最后判断
if find(0) == find(n + 1):
print('Yes')
else:
print('No')