本文共 3453 字，大约阅读时间需要 11 分钟。

题目描述

现有一块大奶酪，它的高度为 $h$，它的长度和宽度我们可以认为是无限大的，奶酪 中间有许多 半径相同 的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中， 奶酪的下表面为 $z=0$ ，奶酪的上表面为 $z=h$ 。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐 标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

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

空间内两点$P_1(x_1,y_1,z_1)$ 、$P_2(x_2,y_2,z_2)$的距离公式如下：

$$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}(P_1,P_2)=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2+(z_1-z_2{)}^2}$$

​

输入格式 每个输入文件包含多组数据。第一行，包含一个正整数 $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

输出 #1

YesNoYes

说明/提示

【输入输出样例1说明】 第一组数据，由奶酪的剖面图可见： 第一个空洞在 $(0,0,0)$ 与下表面相切，第二个空洞在 $(0,0,4)$ 与上表面相切。两个空洞在 $(0,0,2)$ 相切。输出 Yes 。

第二组数据，由奶酪的剖面图可见：两个空洞既不相交也不相切，输出 No 。

第三组数据，由奶酪的剖面图可见：两个空洞相交，且与上下表面相切或相交。输出 Yes 。

【数据规模与约定】

对于 $20\%$ 的数据，$n=1,1\le h,r\le 10,000$ ，坐标的绝对值不超过 $10,000$ 。

对于 $40\%$ 的数据，$1\le n\le 8,1\le h,r\le 10,000$，坐标的绝对值不超过 $10,000$ 。

对于 $80\%$ 的数据，$1\le n\le 1,000,1\le h,r\le 10,000$，坐标的绝对值不超过 $10,000$。

对于$100\%$ 的数据，$1\le n\le 1,000,1\le h,r\le 1,000,000,000,T\le 20$，坐标的绝对值不超过 $1,000,000,000$ 。

---

题意：判断空洞相交或相切形成的路径是否可以从下表面通往上表面。

思路：相交或者相切是一种等价关系。因此可以使用并查集。如果两个空洞相交或者相切，就合并到一个集合中；最后，判断上表面的空洞是否和下表面的空洞在同一个集合中。

代码：注意数据范围！

#include 
   
    using namespace std;const int MAXN = 1100;typedef long long ll;struct sphere {
   	ll x, y, z;} s[MAXN];int father[MAXN];bool isConnected(const sphere &a, const sphere &b, ll r) {
   	double dist = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z); 	return dist <= 4 * r * r;	}void initSet(int n) {
   	for (int i = 0; i < n; ++i) father[i] = -1;	father[1001] = father[1002] = -1; //底部和顶部的特殊位置  }int findSet(int x) {
   	return father[x] < 0 ? x : (father[x] = findSet(father[x]));}void unionSet(int x, int y) {
   	x = findSet(x), y = findSet(y);	if (x == y) return;	if (father[x] < father[y]) {
   		father[x] += father[y];		father[y] = x;	} else {
   		father[y] += father[x];		father[x] = y;	}}int main() {
    	ll t, n, h, r;	scanf("%lld", &t);	while (t--) {
   		scanf("%lld%lld%lld", &n, &h, &r);		initSet(n);		for (int i = 0; i < n; ++i) {
   			scanf("%lld%lld%lld", &s[i].x, &s[i].y, &s[i].z);			if (s[i].z <= r)	 //与底部相交或者相切的空洞与底部合并				unionSet(i, 1001);			if (s[i].z + r >= h) //与顶部相交或者相切的空洞与顶部合并				unionSet(i, 1002);  		}  		for (int i = 0; i < n; ++i)   //遍历全部的空洞, 两两判断是否连通 			for (int j = i + 1; j < n; ++j)  				if (isConnected(s[i], s[j], r))   //连通则合并 					unionSet(i, j);   		printf("%s\n", findSet(1001) == findSet(1002) ? "Yes" : "No");	}	return 0;}
   

转载地址：https://memcpy0.blog.csdn.net/article/details/106662326 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！