#include<bits/stdc++.h>
using namespace std;
int t,n,h,r,x,y,z;
struct center{
long long x,y,z;
bool Used;
}p[1001];
bool ans=0;
long long dist(center p1,center p2)
{
return ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}
void dfs(int m){
if(ans==1) return;
if(h-p[m].z<=r)
{
ans=1;
return;
}
p[m].Used=1;
for(int i=1;i<=n;i++)
{
if(dist(p[m],p[i])<=(4*r*r)&&p[i].Used==0)
{
dfs(i);
}
}
}
int main()
{
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>n>>h>>r;
for(int j=1;j<=n;j++)
{
cin>>p[j].x >>p[j].y >>p[j].z;
p[j].Used =0;
}
for(int i=1;i<=n;i++)
{
if(p[i].z<=r) dfs(i);
}
if(ans==1) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
ans=0;
}
return 0;
}
贴心地附上相似的AC代码(题解的)
#include<bits/stdc++.h>
using namespace std;
int n,v[1005],t,ok;
double x[1005],y[1005],z[1005],h,r;
bool e(int i,int j){
double dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
return dis<=4*r*r;
}
void dfs(int k){
if(ok)return;
if(z[k]+r>=h){
ok=1;
return;
}
v[k]=1;
for(int i=1;i<=n;i++)
if(!v[i]&&e(i,k))
dfs(i);
}
int main(){
cin>>t;
for(int i=1;i<=t;i++){
memset(v,0,sizeof(v));
ok=0;
cin>>n>>h>>r;
for(int j=1;j<=n;j++)
cin>>x[j]>>y[j]>>z[j];
for(int j=1;j<=n;j++)
if(z[j]-r<=0)
dfs(j);
if(ok)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
贴心地附上错误数据之一
2 5100500 1275250
0 0 1275250
0 50500 3825250