并查集40pts WA求助
查看原帖
并查集40pts WA求助
233896
Morre楼主2023/6/25 08:30

求助,蒟蒻查了半天了还是查不出错

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e3+5;
int t,n,h,r,fa[maxn];
vector<int> st,de;
bool flag;
struct node{
	int x,y,z;
}c[maxn];

unsigned long long dist(node p,node q){
	return 1ll*(p.x-q.x)*(p.x-q.x)+1ll*(p.y-q.y)*(p.y-q.y)+1ll*(p.z-q.z)*(p.z-q.z);
}

int findx(int x){
	if(x=fa[x])
		return x;
	else
		return fa[x]=findx(fa[x]);
}

void join(int u,int v){
	fa[findx(u)]=findx(v);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>t;
	while(t--){
		flag=false;
		st.clear();de.clear();
		cin>>n>>h>>r;
		for(int i=1;i<=n;i++){
			fa[i]=i;
			cin>>c[i].x>>c[i].y>>c[i].z;
			if(c[i].z<=r)
				st.push_back(i);
			if(c[i].z+r>=h)
				de.push_back(i);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if((c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y)>4*r*r)
					continue;
				if(dist(c[i],c[j])<=(unsigned long long)4*r*r)
					join(i,j);	
			}			
		}	
		for(auto i : st)
			for(auto j : de)
				if(findx(i)==findx(j)){
					flag=true;
					break;
				}
		flag ? cout<<"Yes"<<endl : cout<<"No"<<endl;
	}
	return 0;
}
2023/6/25 08:30
加载中...