2018-04-02 17:42:25

// luogu-judger-enable-o2
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
using namespace std;
int t;
int f[1001];
double dis(long long x,long long y,long long z,long long x1,long long y1,long long z1){
return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1));
}
int find(int x)
{
if(x==f[x])return x;
else
{
x=f[x];
return find(f[x]);
}
}
long long x[100001],y[100001],z[100001];
int f1[100001],f2[100001];
int main()
{
scanf("%d",&t);
for(int j=1;j<=t;j++)
{
int n,h;
long long r;
int tot1=0,tot2=0;
scanf("%d%d%ld",&n,&h,&r);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=n;i++)
{
scanf("%ld%ld%ld",&x[i],&y[i],&z[i]);
if(z[i]+r>=h){
tot1++;
f1[tot1]=i;
}
if(z[i]-r<=0)
{
tot2++;
f2[tot2]=i;
}
for(int k=1;k<=i;k++)
{
if (dis(x[i],y[i],z[i],x[k],y[k],z[k])<=2*r){
int a1=find(i);
int a2=find(k);
if (a1!=a2)f[a1]=a2;}
}
}
int s=0;
for (int i=1;i<=tot1;i++)
{
for (int k=1;k<=tot2;k++){
if (find(f1[i])==find(f2[k])){
s=1;break; }
}
if (s==1) break;
}
if (s==1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
• star
首页