今天早晨，神志不清的我决定拿头过这道题
终于在wa了6次之后过了
emm 明明都是一些细节自己却注意不到啊啊啊不能再颓了！！！！！！！！！！！！
好了回归正题
首先我们要开long long
其次我们来说一说思路
大佬xcg讲了两种做法
一.搜索
不好想不好写，比第二种算法快
洛谷标签说是广搜，但这个题深搜会比广搜快，因为这里是判断有没有解，而不是让你求最短路
如果要求最短路怎么办？拿头过三维迪杰斯特拉我也不知道
所以我们不讨论怎么求最短路（没有杠精）
我们怎么搜呢？
当然是从下表面开始了（当然也可以从上表面开始，看能否通到下表面，更可以看上下表面哪个洞少就从那个开始搜）
在搜索过程中，就不断找到与当前点相通的点。同时又因为只是判断有没有解，所以只要找到解，就可以直接返回，然后让上一层的程序也返回。这可以用一个标记做到。
问题来了，怎么判断两个洞是否相通？
我们计算两个洞的球心的距离，如果它<=2*r,则证明这两个洞相交或者相切（我也不知道jerry是怎么在相切的时候穿过这一个接触的点的），当等于时，是相切。否则，就不相通。
与底部相通：判断洞的球心的高度-r是否<=0(不是<=h)(我也不知道手残打出来的为什么还有30分)
与顶部相通：球心高度+r>=h
拿头硬过的代码：
#include<bits/stdc++.h> #define ll long long using namespace std; ll read() { char ch=getchar(); ll x=0;bool f=0; while(ch<'0'||ch>'9') { if(ch=='-')f=1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return f?-x:x; } ll t,n,h,r; bool bj,vis[1009]; struct qiu{ ll x,y,z; }p[1009]; bool cmp(qiu a,qiu b)//一个优化退化：按照所有球心的高度进行排序，如果从某个球开始就不与底部相通，则后面的球都不会与底部相通（据lz实测会慢emmmm） { return a.z<b.z; } double jl(qiu a,qiu b) { return sqrt((double)((a.x-b.x)*(a.x-b.x))+(double)((a.y-b.y)*(a.y-b.y))+(double)(a.z-b.z)*(a.z-b.z)); } void dfs(ll k) { if(p[k].z+r>=h) { bj=1;//bj标记有解 return; } for(int i=1;i<=n;i++) { if(bj)return;//若有解则不继续搜索 if(jl(p[k],p[i])<=2.0*r&&!vis[i]) { vis[i]=1; dfs(i); } } } int main() { t=read(); for(ll i=1;i<=t;i++) { memset(vis,0,sizeof(vis)); bj=0; n=read();h=read();r=read(); for(ll j=1;j<=n;j++) p[j].x=read(),p[j].y=read(),p[j].z=read(); sort(p+1,p+1+n,cmp); for(int j=1;j<=n;j++) { if(bj)break; if(p[j].z-r<=0)//可别手残了 { vis[j]=1; dfs(j); } else break; } if(!bj)printf("No "); else printf("Yes "); } }