欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

「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;
}