70分求调
查看原帖
70分求调
1313143
LCK201204楼主2025/1/20 15:17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll T;
ll n,h,r;
ll x[1010],y[1010],z[1010];
bool b[1010],flag;
vector<ll>edges[1010];

inline void dfs(ll i){
	b[i]=true;
	if(flag)return;
	if(i==n+1){
		flag=true;
		return;
	}
	ll l=edges[i].size(); 
	for(ll j=0;j<l;j++){
		if(!b[edges[i][j]]){
			dfs(edges[i][j]);
		}
	}
}

int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld",&n,&h,&r);
		memset(b,false,sizeof(b));
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(z,0,sizeof(z));
		for(ll i=0;i<=1009;i++)edges[i].clear();
		for(ll i=1;i<=n;i++){
			scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
		}
		flag=false;
		for(ll i=1;i<=n;i++){
			for(ll j=i+1;j<=n;j++){
				if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j])>4ll*r*r)continue;
				if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j])<=4ll*r*r){
					edges[i].push_back(j);
					edges[j].push_back(i); 
				}
			}
		}
		for(ll i=1;i<=n;i++){
			if(z[i]<=r){
				edges[i].push_back(0);
				edges[0].push_back(i);
			}
			if(abs(h-z[i])<=r){
				edges[i].push_back(n+1);
				edges[n+1].push_back(i); 
			}
			if(z[i]<=r&&abs(h-z[i])<=r){
				printf("Yes\n");
				flag=true;
			}
		}
		if(!flag)dfs(0);
		if(flag)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
2025/1/20 15:17
加载中...