70分求助,最后3个点没过;
查看原帖
70分求助,最后3个点没过;
316354
乔铎清楼主2022/8/12 11:40
#include <bits/stdc++.h>
using namespace std;
int x[1000000];
int y[1000000];
int z[1000000];
int fa[1000000];
int dis(int x1,int y1,int z1,int x2,int y2,int z2)
{
    int sum = 0;
    sum = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1));
    return sum;
}
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }
    else
    {
        fa[x]=find(fa[x]);
        return fa[x];
    }
}
int main()
{
    int t;
    cin >> t;
    for(int i=1;i<=t;i++)
    {
        int n,h,r;
        cin >> n >> h >> r;
        for(int j=0;j<=n+1;j++)
        {
            fa[j]=j;
        }
        for(int j=1;j<=n;j++)
        {
            cin >> x[j] >> y[j] >> z[j];
            if(z[j]-r<=0)
            {
                if(find(j)!=find(0))
                {
                    fa[find(j)]=find(0);
                }
            }
            if(z[j]+r>=h)
            {
                if(find(j)!=find(n+1))
                {
                    fa[find(j)]=find(n+1);
                }
            }
            for(int p=1;p<j;p++)
            {
                if(dis(x[j],y[j],z[j],x[p],y[p],z[p])<=2*r)
                {
                    if(find(j)!=find(p))
                    {
                        fa[find(j)]=find(p);
                    }
                }
            }
        }
        if(find(n+1)==find(0))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}
2022/8/12 11:40
加载中...