80pts求调
查看原帖
80pts求调
591561
Xianzi_楼主2024/11/9 14:27

rt

#include "bits/stdc++.h"
using namespace std;
struct node{
    long long x, y, z;
} a[100005];
int t, n, h, r;
int f[1005];
long long dist(node p1, node p2){
    return ((p1.x - p2.x) * (p1.x - p2.x) +  (p1.y - p2.y) * (p1.y - p2.y) + (p1.z - p2.z) * (p1.z - p2.z));
}
void init(){
    for (int i = 1; i <= n; i++) f[i] = i;
}
int find(int x){
    if (f[x] == x) return x;
    else return find(f[x]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--){
        int tot1 = 0, tot2 = 0;
        cin >> n >> h >> r;
        int floorr[100005], ceill[100005];
        init();
        for (int i = 1; i <= n; i++){
            cin >> a[i].x >> a[i].y >> a[i].z;
            if (a[i].z - r <= 0) tot1++, floorr[tot1] = i;
            if (a[i].z + r >= h) tot2++, ceill[tot2] = i;
            for (int j = 1; j <= i; j++){
                if (dist(a[i], a[j]) <= 4 * r * r){
                    int p = find(i), q = find(j);
                    if (p != q) f[p] = q;
                }
            }
        }
        bool flag = 0;
        for (int i = 1; i <= tot2; i++){
            for (int j = 1; j <= tot1; j++)
                if (find(ceill[i]) == find(floorr[j]))
                    {flag = 1; break;}
            if (flag) break;
        }
        if (flag) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}
2024/11/9 14:27
加载中...