「NOIP2017」 奶酪 - 并查集
程序员文章站
2022-05-22 13:36:03
...
题目大意
在一个三维空间内有一块长方体奶酪,下表面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;
}