1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <queue>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 
10 const int maxn = 1005;
11 
12 int head[maxn], eid;
13 
14 struct Edge {
15     int v, next;
16 } edge[maxn / 2 * maxn];
17 
18 void insert(int u, int v) {
19     edge[++eid].v = v;
20     edge[eid].next = head[u];
21     head[u] = eid;
22 }
23 
24 int t, n, h, r;
25 int x[maxn], y[maxn], z[maxn], vis[maxn];
26 
27 queue<int> q;
28 
29 inline ll pw2(int x) {return 1LL * x * x;}
30 
31 inline double dis(int i, int j) {
32     return sqrt(pw2(x[i] - x[j]) + pw2(y[i] - y[j]) + pw2(z[i] - z[j]));
33 }
34 
35 inline int bfs() {
36     q.push(0);
37     vis[0] = 1;
38     while (!q.empty()) {
39         int u = q.front();
40         q.pop();
41         if (u == n + 1) {
42             while (!q.empty()) q.pop();
43             return 1;
44         }
45         vis[u] = 1;
46         for (int p = head[u]; p; p = edge[p].next)
47             if (!vis[edge[p].v]) q.push(edge[p].v);
48     }
49     return 0;
50 }
51 
52 int main() {
53     scanf("%d", &t);
54     while (t--) {
55         memset(vis, 0, sizeof(vis));
56         memset(head, 0, sizeof(head));
57         eid = 0;
58         scanf("%d%d%d", &n, &h, &r);
59         for (int i = 1; i <= n; ++i) {
60             scanf("%d%d%d", &x[i], &y[i], &z[i]);
61             if (abs(z[i]) <= r) {insert(0, i); insert(i, 0);}
62             if (abs(1LL * h - z[i]) <= r) {insert(n + 1, i); insert(i, n + 1);}
63         }
64         for (int i = 1; i <= n; ++i)
65             for (int j = i + 1; j <= n; ++j)
66                 if (dis(i, j) <= 2 * r)
67                 {insert(i, j); insert(j, i);}
68         if (bfs()) printf("Yes\n");
69         else printf("No\n");
70     }
71     return 0;
72 }

AC代码

优质内容筛选与推荐>>
1、一道西班牙竞赛题和双曲函数
2、spring 工具类大集合
3、如何查看pip安装包的所有版本；以及ipython的安装
4、[Vue] : 键盘修饰符
5、洛谷AT2046 Namori（思维，基环树，树形DP）