时隔多日，我经历完中考又回来了！
刚刚步入高中生活，又要抽出一部分时间来打信竞，实在是压力山大。
但是，我相信经过竞赛对我的磨砺一定对我的未来大有用处。
所以话不多说，来看今天这道做过很多遍的经典考题。
这道题最主要的目的是判断上下表面的连通性，所以，对于每一个球（可以看作是点）我们只需要关注能否从下表面达到。
想到这里，自然而然地可以想到用深搜来实现这道题。
细节上的问题可以看代码，思路比较容易
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define int long long #define maxn 1010 #define rep(i,s,e) for(register int i=s;i<=e;++i) #define dwn(i,s,e) for(register int i=s;i>=e;--i) using namespace std; inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();} return f*x; } inline void write(int x) { if(x<0){putchar('-');x=-x;} if(x>9)write(x/10); putchar(x%10+'0'); } int T,flag=0; int n; double h,r; int book[maxn]; struct node { double x,y,z; }a[maxn]; bool cmp(node p,node q) { return p.z<q.z; } double dist(double xx,double yy,double zz,double xxx,double yyy,double zzz) { return sqrt((xx-xxx)*(xx-xxx)+(yy-yyy)*(yy-yyy)+(zz-zzz)*(zz-zzz)); } void dfs(node x,int num) { if(x.z+r>=h) { flag=1; return; } book[num]=1; rep(i,1,n) { if(flag==1) return; if(book[i]==0&&dist(x.x,x.y,x.z,a[i].x,a[i].y,a[i].z)<=2*r) { dfs(a[i],i); } } } signed main() { T=read(); while(T--) { flag=0; memset(book,0,sizeof(book)); n=read(); cin>>h>>r; rep(i,1,n) { cin>>a[i].x>>a[i].y>>a[i].z; } sort(a+1,a+n+1,cmp); rep(i,1,n) { if(a[i].z-r<=0) { dfs(a[i],i); } } if(flag==1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }