蒟蒻的第一篇题解
Xrain06
2020-12-25 19:53:53
其实这题暴力(dfs)都可以过。。。\
~~蒟蒻表示不知道怎么用并查集~~
------------
既然是道金题，肯定很简单。
题目要求就是一个三维空间内，有几个圆形空洞，要从这些洞走到顶层。
为什么是圆形？
题目给了两个点的距离公式，而球体的特点就是圆形到球面上的每个点距离相等，这样就很方便判断了。
```cpp
#include<bits/stdc++.h>
using namespace std;
int t,n;
long long h,r;
bool f,f1[1001];
struct node{
long long x;
long long y;
long long z;
}a[1001];
bool cmp(node a,node b){
return a.z<b.z;
}
void dfs(int i){
if(f)return;
if(f1[i])return;//剪枝
if(a[i].z+r>=h){//判断到没到终点
f=1;
return;
}
f1[i]=1;
for(int j=1;j<=n;j++){
if(i==j)continue;
if(sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z))>r*2)continue;//判断能不能到
dfs(j);
}
}
int main(){
cin>>t;
while(t--){
cin>>n>>h>>r;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y>>a[i].z;
}
sort(a+1,a+n+1,cmp);//其实不需要
f=0;
for(int i=1;i<=n;i++){
if(a[i].z>r){
break;
}
memset(f1,0,sizeof(f1));
dfs(i);
if(f){
break;
}
}
if(f)cout<<"Yes";
else cout<<"No";
cout<<'\n';
}
return 0;
}
```