题解：P3958 [NOIP2017 提高组] 奶酪

思路

不妨考虑并查集数据结构，对于并查集这种数据结构不再阐述，相关内容请学会使用搜索引擎。

既然要从一个洞口到另一个洞口，那么就把这两个洞口放到一个集合（即可以通过）里。

那是不是所有的洞口都能合并呢？显然不行，那这样就一定有解了。

怎样才能将两个洞口合并呢？如果两个洞口的圆心的直线距离不大于（即小于或等于）两个半径，就可以将这两个洞口合并。

代码

去年的去年的代码：

#include<bits/stdc++.h> 
using namespace std;
#define maxn 1010
int n,h,r,fa[maxn],T;
int x[maxn],y[maxn],z[maxn];

int find(int x){
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
void uni(int x, int y){
	int rx = find(x), ry = find(y);
	if(rx == ry) return;
	fa[ry] = rx;
}
void init(){for(int i = 0;i <= n+1;i++) fa[i] = i;}
double squ(double x){return x * x;} 
double dis(double x1,double y1,double z1,double x2,double y2,double z2){return (double)((double)squ(x1-x2) + (double)squ((y1-y2)) + (double)squ((z1-z2)));}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>h>>r;
		init();
		for(int i = 1;i <= n;i++){
			cin>>x[i]>>y[i]>>z[i];
			// 进行洞口和洞口（即通道）的合并操作
			if(abs(z[i] - 0) <= r) uni(0,i);
			if(abs(z[i] - h) <= r) uni(n+1,i);
			for(int j = 1;j < i;j++){if(4LL * r * r >= dis(x[i],y[i],z[i],x[j],y[j],z[j])) uni(i,j);}
		}
		if(find(0) == find(n+1)) cout<<"Yes"<<endl; // 判断起点和奶酪表面是不是在一个集合里，也就是说能不能到达
		else cout<<"No"<<endl;
	}
	return 0;
}