这题终于是正经第一题感觉了。
只需要对相交或相切的球建一条边，然后对所有与底面有交点的球连边，再对所有与顶面有交点的球连边，bfs判断上下连通性即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<cstring> 6 #include<cmath> 7 #include<queue> 8 using namespace std; 9 typedef long long ll; 10 struct point 11 { 12 long long x,y,z; 13 }p[1005]; 14 bool v[1005]; 15 double c(point a,point b) 16 { 17 return sqrt(1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y)+1ll*(a.z-b.z)*(a.z-b.z)); 18 } 19 int head[1005],cnt; 20 struct node 21 { 22 int to,nex; 23 }e[2005005]; 24 void add(int x,int y) 25 { 26 e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt; 27 } 28 queue<int>q;int n,h,r; 29 bool bfs() 30 { 31 memset(v,0,sizeof(v)); 32 while(!q.empty())q.pop(); 33 q.push(0);v[0]=1; 34 while(!q.empty()) 35 { 36 int x=q.front();q.pop();if(x==n+1)return 1; 37 for(int i=head[x];i;i=e[i].nex) 38 { 39 int y=e[i].to; 40 if(v[y])continue; 41 q.push(y);v[y]=1; 42 } 43 } 44 return 0; 45 } 46 int main() 47 { 48 //freopen("cheese.in","r",stdin); 49 //freopen("cheese.out","w",stdout); 50 int t; 51 scanf("%d",&t); 52 while(t--) 53 { 54 cnt=0;memset(head,0,sizeof(head)); 55 scanf("%d%d%d",&n,&h,&r); 56 for(int i=1;i<=n;++i) 57 { 58 scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z); 59 } 60 p[0].x=p[0].y=p[0].z=0;p[n+1].x=p[n+1].y=0;p[n+1].z=h; 61 for(int i=1;i<=n;++i) 62 { 63 for(int j=i+1;j<=n;++j) 64 { 65 double dis=c(p[i],p[j]); 66 if(dis>r+r)continue;add(i,j),add(j,i); 67 } 68 } 69 for(int i=1;i<=n;++i) 70 { 71 if(p[i].z<=r&&p[i].z>=-r)add(0,i); 72 if(p[i].z>=h-r&&p[i].z<=h+r)add(i,n+1); 73 } 74 if(bfs())puts("Yes"); 75 else puts("No"); 76 } 77 //fclose(stdin); 78 //fclose(stdout); 79 return 0; 80 }