专栏文章

P3958 题解

iikunTLE
P3958题解参与者 5已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miqmtm37
此快照首次捕获于
2025/12/04 07:22
3 个月前
此快照最后确认于
2025/12/04 07:22
3 个月前
查看原文
题目传送门

思路

可以使用并查集解决此题。
首先将满足 z≥h−rz\ge h-r 的数放入集合 F1F_1 中，将满足 z≤rz\le r 的数放入集合 F2F_2 中。这是因为以上两个条件分别能满足顶面相交和底面相交。
然后判断两个空洞是否相通，只需判断 dist(Pi,Pj)≤2×r\text{dist}(P_i,P_j)\le2\times r 即可。这是因为两圆的圆心距离小于或等于它们的半径之和，两个圆就会相交或刚好相接。如果满足条件，就将 PiP_i 和 PjP_j 通过并查集合并。
最后，判断是否存在 F1,iF_{1,i} 与 F2,jF_{2,j} 相连即可。
注意事项
  • 不开 long long 见祖宗。
AC CODE
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define y1 y_1
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=1e6+10;
int n,h,r,fa[N],x[N],y[N],z[N],f1[N],f2[N];
void _init(){
	for(int i=1;i<=n;++i)
		fa[i]=i;
	return;
}
int _find(int x){
	if(x==fa[x])
		return x;
	fa[x]=_find(fa[x]);
	return fa[x];
}
void _merge(int x,int y){
	int fx=_find(x),fy=_find(y);
	if(fx!=fy)
		fa[fx]=fy;
	return;
}
int dis(int x1,int x2,int y1,int y2,int z1,int z2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2);
}
void solve(){
	n=read(),h=read(),r=read();
	_init();
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;++i){
		x[i]=read(),y[i]=read(),z[i]=read();
		if(z[i]>=h-r)
			f1[++cnt1]=i;
		if(z[i]<=r)
			f2[++cnt2]=i;
		for(int j=1;j<=i;++j){
			if(dis(x[i],x[j],y[i],y[j],z[i],z[j])>4*r*r)
				continue;
			int temp_1=_find(i),temp_2=_find(j);
			if(temp_1!=temp_2)
				_merge(temp_1,temp_2);
		}
	}
	bool flag=false;
	for(int i=1;i<=cnt1;++i){
		for(int j=1;j<=cnt2;++j)
			if(_find(f1[i])==_find(f2[j])){
				flag=true;
				break;
			}
		if(flag)
			break;
	}
	printf(flag?"Yes\n":"No\n");
	return;
}
signed main(){
	short T=read();
	while(T--)
		solve();
	return 0;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...