救救孩子……
查看原帖
救救孩子……
181037
ysmlwudia楼主2020/9/19 10:30
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>

using namespace std;
struct node{
	int x,y,z;
}p[1005];
int t,n,h,r,tot,last[2*1005*1005],mark[1005],flag;
struct edge{
	int prev,to;
}e[2*1000005];
void add(int a,int b){
	e[++tot].prev=last[a],e[tot].to=b;
	last[a]=tot;
}
void dfs(int x){
	if(p[x].z+r>=h){
		flag=1;	
		return;	
	}
	if(flag)return;
	for(int i=last[x];i;i=e[i].prev){
		if(!mark[e[i].to]){
			mark[e[i].to]=1;
			dfs(e[i].to);
		}
	}
}
int main(){
	freopen("P3958_7.in","r",stdin);
	cin>>t;
	while(t--){
		memset(mark,0,sizeof(mark));
		memset(p,0,sizeof(p));
		tot=0;
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			cin>>p[i].x>>p[i].y>>p[i].z;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=i-1;j++){
				int xx=p[i].x,yy=p[i].y,zz=p[i].z;
				int xp=p[j].x,yp=p[j].y,zp=p[j].z;
				if(sqrt((xx-xp)*(xx-xp)+(yy-yp)*(yy-yp)+(zz-zp)*(zz-zp))<=2*r){
					add(i,j);
					add(j,i);
				}
			}
		}
		flag=0;
		for(int i=1;i<=n;i++){
			int xx=p[i].x,yy=p[i].y,zz=p[i].z;
			if(zz-r<=0){
				flag=0;
				mark[i]=1;
				dfs(i);
				if(flag){
					cout<<"Yes"<<endl;
					break;
				}
			}
		}
		if(!flag){
			cout<<"No"<<endl;
		}
		for(int i=1;i<=tot;i++){
			e[i].prev=e[i].to=0;
			last[i]=0;
		}
	}
	return 0;
}

救救孩子,60分第七数据点20组数据只有其中一组数据没过,不知道为什么,那组数据其中一个“No”我输出“Yes”

2020/9/19 10:30
加载中...