改了好久了,样例过了,落谷下载的第一个数据不完整, 求dalao助,有注释,看不懂的可以问
#include <bits/stdc++.h>
#define lll long long
#define re register
using namespace std;
lll q;
lll n,fa[1009];
double r,h;
struct fuck {
double x,y,z;
} p[1009];
lll finds(lll x) {
if(fa[x]==x) return x;
return fa[x]=finds(fa[x]);
}
vector<lll> sbm; //存到了上表面
vector<lll> xbm; //存到了下表面
int main() {
scanf("%d",&q);
while(q--) {
scanf("%lld%lf%lf",&n,&h,&r);
bool flag=1;
for(re lll i=1; i<=n; i++) fa[i]=i; //
for(re lll i=1; i<=n; i++) {
scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
// cout<<p[i].z-r<<" "<<p[i].z+r<<endl;
if(p[i].z-r<=0.0) xbm.push_back(i);
if(p[i].z+r>=h) sbm.push_back(i); //符合条件加入
}
for(re lll i=1; i<n; i++) {
for(re lll j=i+1; j<=n; j++) {
lll y=finds(j),x=finds(i); //并查集找父节点
double cc=sqrt(abs(p[i].z-p[j].z)*abs(p[i].z-p[j].z)+abs(p[i].y-p[j].y)*abs(p[i].y-p[j].y)+abs(p[i].x-p[j].x)*abs(p[i].x-p[j].x));//距离
if(x!=y&&cc<=(r*2)) {
fa[x]=y; //如果相交或相切,连父节点
}
}
}
for(re lll i=0; i<sbm.size(); i++) {
for(re lll j=0; j<xbm.size(); j++) {
if(fa[sbm[i]]==fa[xbm[j]]) {//如果同一父节点,则联通
printf("Yes\n");
flag=0;
break;
}
}
if(flag==0) break;
}
if(flag==1) {
printf("No\n");
flag=0;
}
}
return 0;
}