連結：https://ac.nowcoder.com/acm/problem/16417

來源：牛客網

奶酪（并查集）

題目描述

現有一塊大奶酪，它的高度為 h，它的長度和寬度我們可以認為是無限大的，奶酪中間有許多半徑相同的球形空洞。我們可以在這塊奶酪中建立空間坐标系， 在坐标系中，奶酪的下表面為 z = 0，奶酪的上表面為 z = h。

現在， 奶酪的下表面有一隻小老鼠 Jerry， 它知道奶酪中所有空洞的球心所在的坐标。如果兩個空洞相切或是相交，則 Jerry 可以從其中一個空洞跑到另一個空洞，特别地，如果一個空洞與下表面相切或是相交， Jerry 則可以從奶酪下表面跑進空洞； 如果一個空洞與上表面相切或是相交， Jerry 則可以從空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道， 在不破壞奶酪的情況下，能否利用已有的空洞跑到奶酪的上表面去?

空間内兩點 P1(x1,y1,z1) 、P2(x2,y2,z2) 的距離公式如下：

輸入描述:

每個輸入檔案包含多組資料。

輸入檔案的第一行，包含一個正整數 T，代表該輸入檔案中所含的資料組數。

接下來是 T 組資料，每組資料的格式如下：

第一行包含三個正整數 n， h 和 r， 兩個數之間以一個空格分開，分别代表奶酪中空洞的數量，奶酪的高度和空洞的半徑。

接下來的 n 行，每行包含三個整數 x, y, z， 兩個數之間以一個空格分開， 表示空洞球心坐标為 (x,y,z)。

輸出描述:

輸出檔案包含 T 行，分别對應 T 組資料的答案，如果在第 i 組資料中， Jerry 能從下表面跑到上表面，則輸出“Yes”，如果不能，則輸出“No”（均不包含引号）。

示例1

輸入

3

2 4 1

0 0 1

0 0 3

2 5 1

0 0 1

0 0 4

2 5 2

0 0 2

2 0 4

輸出

Yes

No

Yes

說明

備注:

對于 20%的資料， n = 1， 1 ≤ h , r ≤ 10,000，坐标的絕對值不超過 10,000。

對于 40%的資料， 1 ≤ n ≤ 8， 1 ≤ h , r ≤ 10,000，坐标的絕對值不超過 10,000。

對于 80%的資料，1 ≤ n ≤ 1,000， 1 ≤ h , r ≤ 10,000，坐标的絕對值不超過 10,000。

對于 100%的資料， 1 ≤ n ≤ 1,000， 1 ≤ h , r ≤ 1,000,000,000， T ≤ 20，坐标的絕對值不超過 1,000,000,000。

思路來源牛客網。

作者：limojin

連結：https://ac.nowcoder.com/discuss/199158?type=101&order=0&pos=1&page=0

來源：牛客網

問題中有兩個需要注意的點，一個是空洞和空洞有合并的情況，另一個是合并後空洞的最大高度。是以，合并父節點的情況可以采用并查集的方式來維護，而對于最大高度的情況，思路是儲存每個空洞的最高點，然後查詢空洞根父親節點的高度。然而這種思路還有一個比較重要的注意事項，即：能否有一個空洞的最低點小于0。如果所有空洞的最低點都大于0，一定是不可以的。是以維護一個st數組來保證哪些節點最低點是小于0的，以此保證其根父親節點有意義。

另外，雖然最開始采用的是dis的平方進行比較，但考慮到r資料範圍到1e9，是以應該采用開方後比較，并使用ll。

由于感覺作者的代碼太麻煩，個人在了解思路後，自己編寫了新的代碼可供參考。

代碼如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long int ll;
const ll MAXN = 1e3 + 10;
ll n, h, r;
ll cnt = 0;
ll f[MAXN];
ll vis[MAXN];
ll len[MAXN];

struct Node
{
	ll x, y, z;
}nod[MAXN];

void init()
{
	for (ll i = 0; i < n; i++)
		f[i] = i;
	cnt = 0;
	memset(len, 0, sizeof(len));
	memset(vis, 0, sizeof(vis));
	return;
}

ll dis(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2)
{
	return (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1);
}

ll find(ll x)
{
	if (f[x] == x)
		return x;
	return(f[x] = find(f[x]));
}

ll merge(ll x, ll y)
{
	ll f1 = find(x);
	ll f2 = find(y);
	if (f1 == f2)
		return 0;
	else
	{
		if (vis[f1] > vis[f2])
		{
			f[f2] = f1;
		}
		else
			f[f1] = f2;
		return 1;
	}
}

int main()
{
	ll T;
	cin >> T;
	while (T--)
	{
		cin >> n >> h >> r;
		init();
		for (ll i = 0; i < n; i++)
		{
			cin >> nod[i].x >> nod[i].y >> nod[i].z;
			vis[i] = nod[i].z + r;
			if (nod[i].z - r <= 0)
				len[cnt++] = i;
		}
		for (ll i = 0; i < n; i++)
		{
			for (ll j = 0; j < i; j++)
			{
				if (sqrt(1.0 * dis(nod[i].x, nod[i].y, nod[i].z, nod[j].x, nod[j].y, nod[j].z))<2*r+(1e-9))
					merge(i, j);
			}
		}
		ll flag = 0;
		for (ll i = 0; i < cnt; i++)
		{
			if (vis[find(len[i])] >= h)
			{
				flag = 1;
				cout << "Yes" << endl;
				break;
			}
		}
		if (flag == 0)
			cout << "No" << endl;
	}
	return 0;
}