70分,大佬求调(有详细注释)
查看原帖
70分,大佬求调(有详细注释)
1380473
ZY_202301005129楼主2024/8/28 18:21
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct d
{
	int x, y, z;
};
int fa[1001];//记录节点的爹
d a[1001];//记录每个洞的数据
int n, h, r;
bool judge(d a, d b)
{
	return b.z > a.z;
}
bool touch(int x, int y)//判断是否链接
{
	double wc = sqrt(pow(a[x].x - a[y].x, 2) + pow(a[x].y - a[y].y, 2) + pow(a[x].z - a[y].z, 2));
	if ( wc<= 2 * r)
		return 1;
	else return 0;
}
int refa(int x)//找祖宗节点
{
	if (fa[x] == x)
		return x;
	else return refa(fa[x]);
}
void ad(int x, int y)//合并并查集
{
	int x1 = refa(x);
	int y1 = refa(y);
	fa[y1] = x1;
}
signed main()
{
	int t;cin >> t;
	while (t--)
	{
		int top1=0, low1=0;
		cin >> n >> h >> r;
		int sign = 0;
		for (int i = 1;i <= n;i++)
		{
			cin >> a[i].x >> a[i].y >> a[i].z;
			if (a[i].z + r >= h)top1++;//统计能链接顶部的洞
			if (a[i].z - r <= 0)low1++;//统计能链接底部的洞
			if (a[i].z + r >= h && a[i].z - r <= 0)
			{
				if (!sign)
				{
				sign = 1;
				cout << "Yes" << "\n";//如果有一个洞可以同时联通底部和顶部,那么一定能联通
				}
			}
		}
		if (sign)continue;//已经知道可以联通了,所以不再进行判断
		for (int i = 1;i <= n;i++)//并查集初始化
			fa[i] = i;
		sort(a + 1, a + 1 + n, judge);//按照高度从小到大进行排序
		for (int i = 1;i <= n;i++)
		{
			for (int j = 1;j < i;j++)//对当前遍历的洞,与之前已经遍历的洞进行判断,看看是否能够连接上
			{
				if (touch(i, j))////如果能与这个洞链接,那么自然是这个洞高度越小越好,所以发现第一个能链接父节点之后就停止判断
				{
					ad(j, i);
					if (n - i < top1 && refa(i) <= low1)//如果当前洞是那些能联通顶部的洞之一,且祖宗洞也是能链接底部的洞
					{//说明可以联通
						cout << "Yes" << "\n";
						sign = 1;
					}
					break;
				}
			}
			if (sign)break;//已经找到联通的了,这个样例不需要再判断了
		}
		if (!sign)cout << "No" << "\n";
	}
}
2024/8/28 18:21
加载中...