题解

题目分析

这是一道算法题目，需要根据具体题目要求进行求解。

解题思路

1. 问题分析

• 仔细阅读题目描述，理解题目要求
• 分析输入输出格式和约束条件
• 确定需要使用的算法和数据结构

2. 算法选择

• 根据题目特点选择合适的算法
• 考虑时间复杂度和空间复杂度
• 确保算法能正确处理所有测试用例

3. 实现要点

• 注意边界条件的处理
• 优化输入输出以提高效率
• 确保代码的正确性和鲁棒性

4. 调试和优化

• 使用测试用例验证算法正确性
• 分析性能瓶颈并进行优化
• 确保代码能通过所有测试点

注意事项

• 仔细处理数据类型和精度问题
• 注意数组越界和空指针问题
• 确保算法的时间复杂度符合要求

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 5;

int x[N], y[N], z[N], vis[N];
int n, h, r;
string ans;
ll dis(int i, int j) {
    return 1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j]) + 1LL * (z[i] - z[j]) * (z[i] - z[j]);
}

void dfs(int u) {
    vis[u] = 1;
    if (ans == "Yes") return;
    if (z[u] >= h - r) {
        ans = "Yes";
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && dis(u, i) <= 4LL * r * r) {
            dfs(i);
        }
    }
}

void solve() {
    ans = "No";
    cin >> n >> h >> r;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> z[i];
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i] && z[i] <= r) {  // 和地面相交
            dfs(i);
        }
    }

    cout << ans << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }    
    return 0;
}