社区讨论

20分求助

P3958[NOIP 2017 提高组] 奶酪参与者 2已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lo7uph7d
此快照首次捕获于
2023/10/27 08:04
2 年前
此快照最后确认于
2023/10/27 08:04
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int T,n,h,x,y,z,t,j[21],p;
long long r;
const long MAXN=10000001;
long long xx[MAXN],yy[MAXN],zz[MAXN];
bool vis[1001];
int d(long long aa,long long bb,long long cc,long long d,long long e,long long f){
	return sqrt((aa-d)*(aa-d)+(bb-e)*(bb-e)+(cc-f)*(cc-f));
}
void dfs(int k){
	    if(t==1)return;
	    if(zz[k]+r>=h){
	    		p++;
	    		j[p]=1;
	    		t=1;
	    		return;
		}
	    vis[k]=1;
	    for(int i=1;i<=n;i++){
	    	if(!vis[i]&&d(xx[k],yy[k],zz[k],xx[i],yy[i],zz[i])<=r*2){
	    		vis[i]=1;
	    	    dfs(i);
	    	    vis[i]=0;
	    	}
	    }
		
}
int main(){
	cin>>T;
	for(int i=1;i<=T;i++){
		cin>>n>>h>>r;
	for(int i=1;i<=n;i++){
		cin>>x>>y>>z;
	    xx[i]=x;
	    yy[i]=y;
	    zz[i]=z;
	}
	t=0;
	dfs(1);
	if(t==0)p++;
}
    for(int i=1;i<=p;i++){
    	if(j[i]==1)cout<<"Yes"<<endl;
    	if(j[i]==0)cout<<"No"<<endl;
    }
	return 0;
}

回复

7 条回复,欢迎继续交流。

正在加载回复...