题目来源如题（滑稽；
我当年去NOIP考这题是懵x的，我也不知道当时写了啥。。。。
--------------------------------------------------------------正经分割-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解：
这题主要内容就是在空间直角坐标系中找到一些相切或相交的球使他们放在一起成为一条从底通到顶的道路（通天大路：滑稽）。
基本想法就是把每一个可以成为路的球的集合都拿出来，然后判断他们是否合法，只要有一个是合法的那么输出Yes，如果都没有就输出No。
然后我们想如何把合法的球连起来，考虑并查集，这样我们相当于以这个并查集的根作为这个并查集的标号来代表这以条路径。然后维护一个jud二维数组
jud【i】【1】代表这个集合中接上层的球是否存在，jud【i】【2】代表这中接下层的球是否存在，都存在的话那么这个集合就是合法的。
分析复杂度，第一步是O（n*n）的处理并查集，第二步是O（n）的查找，总体是O（n*n）的复杂度，n属于【1,1000】O（n*n）稳过。
代码：
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const long long maxn=2000;
long long x[maxn],y[maxn],z[maxn],bel[maxn],abo[maxn],jud[maxn][3],f[maxn];
long long fang(long long x){ return x*x; }//平方
long long getdis(long long i,long long j){//求两点间距离
long long xx=x[i];long long yy=y[i];long long zz=z[i];
long long x2=x[j];long long y2=y[j];long long z2=z[j];
long long rtt=fang(x2-xx)+fang(y2-yy)+fang(z2-zz);
return rtt;
}
long long find(long long x){//并查集
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
void mem(){//初始化
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(z,0,sizeof(z));
memset(bel,0,sizeof(bel));
memset(abo,0,sizeof(abo));
memset(jud,0,sizeof(jud));
memset(f,0,sizeof(f));
}
int main(){
long long t;
scanf("%lld",&t);
while(t--){
long long n,h,r,flag=0;
mem();
scanf("%lld%lld%lld",&n,&h,&r);//r要开long long,我这里顺手全开了。。。
for(long long i=1;i<=n;i++)scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
for(long long i=1;i<=n;i++){
f[i]=i;
if(z[i]-r<=0)bel[i]=true;//贴地
if(z[i]+r>=h)abo[i]=true;//贴顶
}
for(long long i=1;i<=n;i++){
for(long long j=i+1;j<=n;j++){
long long fi=find(i),fj=find(j);
if(fi==fj)continue;
long long rtt=getdis(i,j);
if(rtt>4*r*r)continue;//不把距离开方而是把r平方这样可以减小误差，但是这样r*r会炸int
f[fi]=fj;
}
}
for(long long i=1;i<=n;i++){
long long o=find(i);
if(bel[i]) jud[o][1]++;//贴地
if(abo[i]) jud[o][2]++;//贴顶
if(jud[o][1]&&jud[o][2]){
flag=1; break;
}
}
if(flag==1)printf("Yes");
else printf("No");
if(t)printf("\n");
}
return 0;
}
NOIP2017 DAY2 T1 Cheese
原文：https://www.cnblogs.com/wara209/p/9366043.html
