「Luogu P3958」奶酪

Description

共 $T$ 组数据。在一个三维坐标系上,有 $n$ 个球体,坐标分别为 $(x_i, y_i, z_i)$,半径为 $r$ 。现在从 $z$ 轴的 $0$ 位置出发,所经过的位置一定要有球体覆盖,求能否到达 $z$ 轴的 $h$ 位置。

$(1 \leq n \leq 10^3,1 \leq h,r \leq 10^9,T \leq 20$,坐标的绝对值不超过 $10^9)$

Source

[Luogu]P3958

Solution

考虑用 并查集 维护球体形成的连通块。

如何判断两个球体是否连通?

这就要用到三维空间中的欧式距离公式:

若两个球体球心之间的欧式距离 $|AB| \leq 2r$,则说明这两个球体相交或者相切,可以把它们合并到同一个连通块中。

对于每个连通块,如果与底面和顶面都相连,就能够到达,反之则不行。时间复杂度为 $O(n^2)$ 。

由于求欧式距离时存在精度误差,我们可以将不等式两边开平方,得到

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e3;
int t, n, h, r, x[MAXN + 5], y[MAXN + 5], z[MAXN + 5], d[MAXN + 5], u[MAXN + 5];

inline LL dist(int i, int j) {//三维空间内两点间欧式距离的平方
return (LL) (x[i] - x[j]) * (x[i] - x[j]) + (LL) (y[i] - y[j]) * (y[i] - y[j])
+ (LL) (z[i] - z[j]) * (z[i] - z[j]);
}

struct ufSet {
int fa[MAXN + 5];

ufSet(int n) {
for (int i = 1; i <= n; ++i) fa[i] = i;
}
int find(int x) {
return x != fa[x] ? fa[x] = find(fa[x]) : x;
}
inline void merge(int x, int y) {
fa[find(x)] = find(y);
}
};

int main() {
for (read(t); t; --t) {
read(n), read(h), read(r);
for (int i = 1; i <= n; ++i) read(x[i]), read(y[i]), read(z[i]);
ufSet s(n);
memset(d, 0, sizeof (d));
memset(u, 0, sizeof (u));
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
if (dist(i, j) <= (LL) 4 * r * r)
//为避免精度误差,这里对不等式两边开平方
s.merge(i, j);//合并到同一个连通块中
bool flag = 0;
for (int i = 1; i <= n; ++i) {
if (z[i] - r <= 0) d[s.find(i)] = 1;//与底面相连
if (z[i] + r >= h) u[s.find(i)] = 1;//与顶面相连
if (d[s.find(i)] && u[s.find(i)]) {//如果一个连通块与底面和顶面都相连
flag = 1;
break;
}
}
puts(flag ? "Yes" : "No");
}
return 0;
}

本文标题:「Luogu P3958」奶酪

文章作者:Heartlessly

发布时间:2019年06月19日 - 07:30:57

最后更新:2019年10月14日 - 19:50:24

原始链接:https://heartlessly.github.io/problems/luogu-p3958/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%