70pts,开long long,样例过但7,8,9没过求调!
查看原帖
70pts,开long long,样例过但7,8,9没过求调!
109678
Marshall_Left楼主2024/8/27 22:00
#include<bits/stdc++.h>
using namespace std;
double h,r;
int n;
struct node{
    double x,y,z;
}ho[10001];
bool cmp(node a,node b){
    return a.z<b.z;
}
int fa[10001];
int find(int x){
    if(x==fa[x])
    return x;
    else
    return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    int p=find(x),q=find(y);
    if(p!=q)
    fa[y]=p;
    return ;
}
double dist(int a,int b){
    return sqrt(pow(ho[a].x-ho[b].x,2)+pow(ho[a].y-ho[b].y,2)+pow(ho[a].z-ho[b].z,2));
} 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>h>>r;
        bool flag=0;
        for(int i=1;i<=n;i++)
        fa[i]=i;
        for(int i=1;i<=n;i++)
            cin>>ho[i].x>>ho[i].y>>ho[i].z;
        sort(ho+1,ho+n+1,cmp);
        if(ho[n].z<h-r)
        {
            cout<<"No"<<endl;
            continue;
        }//This sentence's of no impact on 70pts.(Better,Maybe)
        int from=0,tow=0;//1-"from":beginners,"to"-n:enders
        for(int i=1;i<=n;i++){
            if(ho[i].z<=r)
            from++;
               if(ho[i].z>=h-r)
                    tow++;
                for(int j=i-1;j>=1;j--)
                if(dist(i,j)<=2*r)
                merge(j,i);
        }
        for(int i=n;i>n-tow;i--)
        if(find(i)<=from){
            cout<<"Yes"<<endl;
            flag=1;
            break;
        }
        if(!flag)
        cout<<"No"<<endl;
    }
    return 0;
}
2024/8/27 22:00
加载中...