本文主要是介绍「NOIP2017」 奶酪 - 并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意
在一个三维空间内有一块长方体奶酪，下表面z=0，高度为h，长宽无限，其中有一些可以通过的空洞，如果两个洞相交或相切，就可以从一个空洞跑到另一个空洞。给定h和每个空洞的球心坐标和半径，问能否从下表面跑到上表面。
分析
首先要明白对于两个球体A,B如果AB的球心距离小于等于两半径和，两球相切或相交。然后，维护一个并查集，建立一个超级起点z=0和超级终点z=h，如果两个球连通，就将它们并起来，如果与下表面相切，就与超级起点并起来，与上表面相切，就与超级终点并起来。最后查看起点与终点是否在同一个并查集内即可。
代码
#include <cstdio>
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
ll T,n;
double h,r,low,high;
int f[1010];
struct ball {double x,y,z;
}s[1010];
double dist(ball a,ball b) {double x=a.x-b.x,y=a.y-b.y,z=a.z-b.z;return sqrt(x*x+y*y+z*z);
}
int getf(int x) {if (f[x]==x) return x;return f[x]=getf(f[x]);
}
void Union(int x,int y) {x=getf(x);y=getf(y);if (x!=y) f[y]=f[x];
}
int main() {scanf("%lld",&T);while (T--) {scanf("%lld%lf%lf",&n,&h,&r);low=h;high=0;for (int i = 1;i <= n;i++) {scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].z);low=min(low,s[i].z);high=max(high,s[i].z);}if (low-r>0||high+r<h) {printf("No\n");continue;}for (int i = 0;i <= n+1;i++) f[i]=i;for (int i = 1;i <= n;i++) {if (s[i].z-r<=0) Union(0,i);if (s[i].z+r>=h) Union(i,n+1);}for (int i = 1;i < n;i++)for (int j = i+1;j <= n;j++)if (dist(s[i],s[j])<=2*r)Union(i,j);if (getf(0)==getf(n+1)) printf("Yes\n");else printf("No\n");}return 0;
}
这篇关于「NOIP2017」 奶酪 - 并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
