超级水的并没有用什么几何知识的几何题……
直接爆搜一遍最后判断有没有与上/下表面相连的球之间连通即可……O(n2)不动脑子的复杂度
最多只是用一下并查集来判断两个点是否连通……
具体细节不必赘述代码如下（超简洁只有51行）
#include<cstdio>
#include<cmath>
using namespace std;
struct ball
{
long long x,y,z;//开成long long防止运算溢出
}balls[];//存储球心信息
int up[],down[],tot1,tot2;//和上表面/下表面接触的球的球心编号及数组的大小标记
int fa[];//并查集组件
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}//寻找父亲
double dis(ball i,ball j){return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y)+(i.z-j.z)*(i.z-j.z));}//求球心矩
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
for(int i=;i<=;i++)
fa[i]=i;//初始化fa数组
tot1=tot2=;
int n,h,r;
scanf("%d%d%d",&n,&h,&r);
for(int i=;i<=n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
balls[i].x=x;balls[i].y=y;balls[i].z=z;
if(z+r>=h)//球与上表面相交
up[++tot1]=i;
if(z-r<=)//球与下表面相交
down[++tot2]=i;
}
for(int i=;i<=n;i++)//判断任意两个球是否相交
for(int j=i+;j<=n;j++)
if(dis(balls[i],balls[j])<=*r)
fa[getfa(i)]=getfa(j);//若相交，合并
bool ans=false;
for(int i=;i<=tot1;i++)
for(int j=;j<=tot2;j++)
if(getfa(up[i])==getfa(down[j]))//如果从上面与下面相通，则为真
{
ans=true;
break;
}
if(ans)
printf("Yes\n");
else
printf("No\n");
}
return ;
}
我只想提醒一点……判断球是否与上下表面相邻（读入处理的地方）一定一定不要加else！因为一个球可能同时与上下表面相连！我随手加个else30分就没有了………………