0求助(调了1.5h了)
查看原帖
0求助(调了1.5h了)
577421
Irithyll楼主2023/6/30 14:32
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int T,n,h,r,x[maxn],y[maxn],z[maxn],flag,f,m[maxn];
vector<int>G[maxn]; 
void dfs(int u){
	if(h-z[u]<=r){
		f=1;return;
	}
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		
		if(!m[v])dfs(v);
	}
}
int main(){
	cin>>T;
	for(int i=1;i<=T;i++){
		flag=0,f=0;
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(z,0,sizeof(z));
		memset(m,0,sizeof(m));
		for(int j=0;j<=n;j++)G[j].clear();
		cin>>n>>h>>r;
		for(int j=1;j<=n;j++){
			scanf("%d%d%d",&x[j],&y[j],&z[j]);
		}
		for(int j=1;j<=n;j++){
			for(int k=j+1;k<=n;k++){
				if((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])+(z[j]-z[k])*(z[j]-z[k])>4*r*r)continue;
				if(z[j]>z[k])G[k].push_back(j);
				else G[j].push_back(k);
			}
		}
		for(int j=1;j<=n;j++){
			if(z[j]<=r){
				dfs(j);
				if(f){
					flag=1;break;
				}
			}
		}
		if(flag)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
2023/6/30 14:32
加载中...