解题思路
依此枚举出两个点,若它们相交或相切则给它们建立关系(并查集
)。对每个入点和每个出点检查它们之间否有关系,若有关系则说明$Jerry$可以穿过奶酪。
- 如果$z+r \geq h$则说明该点是一个出点。
- 如果$z-r \leq 0$则说明该点是一个入点。
并查集(Accepted)
for _ in range(int(input())):
n, h, r = map(int, input().split())
axis = [list(map(int, input().split())) for _ in range(n)]
vis = [0] * (n + 1)
p = [i for i in range(n+1)]
def distance(x1, y1, z1, x2, y2, z2):
return ( (x1-x2)**2 + (y1-y2)**2 + (z1 - z2)**2 )**0.5
def find(x):
if x == p[x]:
return x
p[x] = find(p[x])
return p[x]
def merge(x, y):
xRoot = find(x)
yRoot = find(y)
p[xRoot] = yRoot
def query(x, y):
return find(x) == find(y)
for i in range(n):
x1, y1, z1 = axis[i]
for j in range(i+1, n):
x2, y2, z2 = axis[j]
if distance(x1, y1, z1, x2, y2, z2) <= 2 * r:
merge(i, j)
flag = False
for i in range(n):
x1, y1, z1 = axis[i]
if flag: break
if z1 - r > 0: continue
for j in range(n):
x2, y2, z2 = axis[j]
if z2 + r >= h:
if query(i, j):
flag = True
break
if flag: print('Yes')
else: print('No')
DFS(过40%)
for i in range(int(input())):
n, h, r = map(int, input().split())
axis = [list(map(int, input().split())) for _ in range(n)]
vis = [0] * (n + 1)
p = [i for i in range(n+1)]
def distance(x1, y1, z1, x2, y2, z2):
return ( (x1-x2)**2 + (y1-y2)**2 + (z1 - z2)**2 )**0.5
def dfs(x, y, z):
global flag
if z + r >= h:
flag = True
return
for i in range(n):
if vis[i]: continue
x1, y1, z1 = axis[i]
if distance(x, y, z, x1, y1, z1) <= 2 * r:
vis[i] = 1
dfs(x1, y1, z1)
vis[i] = 0
flag = False
for i in range(n):
if flag: break
if axis[i][2] - r <= 0:
vis[i] = 1
dfs(axis[i][0], axis[i][1], axis[i][2])
vis[i] = 0
if flag: print('Yes')
else: print('No')
膜拜大佬,在并查集find函数中的
p[x] = find(p[x])有什么作用啊?
这样可以实现路径压缩,你可以搜一下带路径压缩的并查集,主要是防止并查集查询过程退化成链。
明白了,感谢大佬