已开longlong dfs 80pts WA#8#10求调
查看原帖
已开longlong dfs 80pts WA#8#10求调
992003
SAS_Ghost楼主2024/8/7 12:11
#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+10;
typedef long long ll;
ll T,vis[N],head[N],nxt[N],to[N],cnt;
struct point{
	ll x,y,z;
	bool top;
}pts[N];
ll dist(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
void add(ll u,ll v){
	nxt[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
}
void connect(ll a,ll b,ll r){
	point A=pts[a],B=pts[b];
	if(dist(A,B)>2*r)return;
	if(A.z>B.z)add(b,a);
	else if(A.z==B.z)add(a,b),add(b,a);
	else add(a,b);
}
bool dfs(ll u){
	vis[u]=1;
	if(pts[u].top)return 1;
	for(ll i=head[u];i;i=nxt[i]){
		ll v=to[i];
		if(!vis[v])if(dfs(v))return 1;
	}
	return 0;
}
bool run(ll n,ll h,ll r){
	cnt=0;
	memset(vis,0,sizeof(vis));
	memset(head,0,sizeof(head));
	
	for(ll i=1;i<=n;i++){
		point P;
		P.x=pts[i].x;P.y=pts[i].y;P.z=0;
		if(dist(P,pts[i])<=r){
			add(0,i);
		}
		P.z=h;
		if(dist(P,pts[i])<=r){
			pts[i].top=1;
		}
		for(ll j=i+1;j<=n;j++){
			connect(i,j,r);
		}
	}
	return dfs(0);
}
signed main(){
	cin>>T;
	while(T--){
		ll n,h,r;
		cin>>n>>h>>r;
		for(ll i=1;i<=n;i++){
			cin>>pts[i].x>>pts[i].y>>pts[i].z;
			pts[i].top=false;
		}
		bool result=run(n,h,r);
		if(result){
			cout<<"Yes"<<endl;
		}else{
			cout<<"No"<<endl;
		}
	}
	return 0;
}
2024/8/7 12:11
加载中...