并查集0分全wa求助
查看原帖
并查集0分全wa求助
479851
pujingcat楼主2021/10/10 18:52

改了好久了,样例过了,落谷下载的第一个数据不完整, 求dalao助,有注释,看不懂的可以问

#include <bits/stdc++.h>
#define lll long long
#define re register
using namespace std;
lll q;
lll n,fa[1009];
double r,h;
struct fuck {
	double x,y,z;
} p[1009];
lll finds(lll x) {
	if(fa[x]==x) return x;
	return fa[x]=finds(fa[x]);
}
vector<lll> sbm; //存到了上表面 
vector<lll> xbm; //存到了下表面 
int main() {
	scanf("%d",&q);
	while(q--) {
		scanf("%lld%lf%lf",&n,&h,&r);
		bool flag=1;
		for(re lll i=1; i<=n; i++) fa[i]=i; //
		for(re lll i=1; i<=n; i++) {
			scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
			//		cout<<p[i].z-r<<" "<<p[i].z+r<<endl;
			if(p[i].z-r<=0.0) xbm.push_back(i);  
			if(p[i].z+r>=h) sbm.push_back(i); //符合条件加入 
		}
		for(re lll i=1; i<n; i++) {
			for(re lll j=i+1; j<=n; j++) {
				lll y=finds(j),x=finds(i); //并查集找父节点 
				double cc=sqrt(abs(p[i].z-p[j].z)*abs(p[i].z-p[j].z)+abs(p[i].y-p[j].y)*abs(p[i].y-p[j].y)+abs(p[i].x-p[j].x)*abs(p[i].x-p[j].x));//距离 
				if(x!=y&&cc<=(r*2)) {
					fa[x]=y;  //如果相交或相切,连父节点 
				}
			}
		}
		for(re lll i=0; i<sbm.size(); i++) {
			for(re lll j=0; j<xbm.size(); j++) {
				if(fa[sbm[i]]==fa[xbm[j]]) {//如果同一父节点,则联通  
					printf("Yes\n");
					flag=0;
					break; 
				}
			}
			if(flag==0) break;
		}
		if(flag==1) {
			printf("No\n");
			flag=0;
		}
	}
	return 0;
}
2021/10/10 18:52
加载中...