用的dfs,WA50分求调QAQ
查看原帖
用的dfs,WA50分求调QAQ
672632
Betty1236楼主2023/10/5 13:03
#include <iostream>
#include <cmath>
#include <string.h>
using namespace std;
struct hole{
	long int x;
	long int y;
	long int z;
}ho[114514];
long int n,h,r;
int o=0;
bool vis[114515]={false};
double dist(hole h1,hole h2){
	return sqrt((h1.x-h2.x)*(h1.x-h2.x)+(h1.y-h2.y)*(h1.y-h2.y)+(h1.z-h2.z)*(h1.z-h2.z));
}
bool ok(hole h1,hole h2,int r){
	if(dist(h1,h2)<=2*r){
		return true;
	}
	else return false;
}
void dfs(int k){
	if(ho[k].z+r>=h){
		o=1;
		return;
	}
	vis[k]=true;
	for(int i=0;i<n;i++){
		if(ok(ho[i],ho[k],r)&&(vis[i]==false)){
			dfs(i);
		}
	}
}
int main(){
	int t;
	cin>>t;
	for(int q=0;q<t;q++){
		cin>>n>>h>>r;
		for(int i=0;i<n;i++){
			cin>>ho[i].x>>ho[i].y>>ho[i].z;
		}
		for(int i=0;i<n;i++){
			if(ho[i].z<=r){
				dfs(i);
				if(o==1){
					cout<<"Yes"<<endl;
					break;
				}
				memset(vis,false,sizeof(bool)); 
			}
		}
		if(o==0){
			cout<<"No"<<endl;
		}
		o=0;
		memset(vis,false,sizeof(bool));
	}
}
2023/10/5 13:03
加载中...