救救10分的苦逼孩子吧!
查看原帖
救救10分的苦逼孩子吧!
262942
Bonfire_Lit楼主2020/8/15 20:50
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
long long t,fa[10002][2];
bool yo[10002];
struct ho {
	int x,y,z;
};
int find(int x) {//找根
	if(x==fa[x][0])return x;
	return fa[x][0]=find(fa[x][0]);
}
void unit(int x,int y) {
	int z1=find(x),z2=find(y);
	fa[z1][0]=z2;
	fa[z2][1]=z1;//合并
}
long double dis(ho a,ho b) {//算距离
	return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2));
}
bool pd(ho a,ho b,int r) { //判断是不是连着的
	return 2*r>=dis(a,b);
}
bool yijia(int a, int b) {
	return find(a)==find(b);
}
int main() {
	scanf("%lld",&t);
	for(int k=1; k<=t; k++) {
		long long n,h,r;//洞的数量,奶酪高度,洞的半径
		ho hole[10002];
		long long cnt=0;
		scanf("%lld%lld%lld",&n,&h,&r);
		for(long long i=1; i<=n; i++) {
			fa[i][0]=i;
			fa[i][0]=0;
		}
		for(long long i=1; i<=n; i++) {
			scanf("%lld%lld%lld",&hole[i].x,&hole[i].y,&hole[i].z);
		}
		for(long long i=1; i<=n; i++) {
			for(long long j=1; j<=n; j++) {
				if(pd(hole[j],hole[i],r)) {
					unit(i,j);
				}
			}
		}
		bool ac=0;
		for(long long i=1; i<=n&&!ac; i++) {
			for(long long j=1; j<=n&&!ac; j++) {
				if(hole[i].z+r>=h&&hole[j].z<=h&&yijia(i,j)) {
					ac=1;
					break;
				}
				if(hole[j].z+r>=h&&hole[i].z<=h&&yijia(i,j)) {
					ac=1;
					break;
				}
			}
		}
		if(ac)yo[k]=1;
		else yo[k]=0;
	}
//	printf("%d",t);
	for(int i=1; i<=t; i++) {
		if(yo[i])printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

嘤嘤嘤样例都过不去我枯了

2020/8/15 20:50
加载中...