大佬救救80分的孩子吧
查看原帖
大佬救救80分的孩子吧
236299
GUN_楼主2021/7/15 19:50
#include<bits/stdc++.h>
using namespace std;
int t,n,h,r,x[1001],y[1001],z[1001],fa[1001],a,xia[1001],shang[1001];
double dis[1001][1001];
void dist(int a,int b)
{
    double u=(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])+(z[a]-z[b])*(z[a]-z[b]);
    dis[a][b]=sqrt(u);
}
int find(int s)
{
	if(fa[s]!=s) 
	     return find(fa[s]);
	else
	     return s;
}
void un(int a,int b)
{
	if(find(a)!=find(b))
	     fa[find(b)]=find(a);
}
int main()
{
	cin>>t;
	for(int j=1;j<=t;j++)
	     {
	     	  memset(shang,0,sizeof(shang));
	     	  memset(xia,0,sizeof(xia));
	     	  cin>>n>>h>>r;
	     	  for(int i=1;i<=n;i++)
	     	       {
	     	       	    int xx,yy,zz;
	     	       	    cin>>xx>>yy>>zz;
	     	       	    x[i]=xx;
	     	       	    y[i]=yy;
	     	       	    z[i]=zz;
	     	       }
	     	  for(int i=1;i<=n;i++)
	     	       fa[i]=i;
	     	  for(int i=1;i<=n;i++)
	     	       for(int k=1;k<=n;k++)
	     	            if(i!=k)
	     	                 {
	     	                 	  dist(i,k);
	     	                 	  dist(k,i);
	     	                 }
	     	  for(int i=1;i<=n;i++)
	     	       for(int k=1;k<=n;k++)
	     	       	    if(dis[i][k]<=2*r&&find(i)!=find(k))
	     	       	         un(i,k);
	     	  int b=1;
			  for(int i=1;i<=n;i++)
	     	       {
	     	       	    if(z[i]<=r)
	     	       	         xia[find(i)]=1;
	     	            if(h-z[i]<=r)
	     	                 shang[find(i)]=1;
	     	            if(shang[fa[i]]==1&&xia[fa[i]]==1)
	     	                 b=0;
	     	        } 
	     	  if(b==0)
	     	       cout<<"Yes"<<endl;
	     	  else
	     	       cout<<"No"<<endl;
	     }
	return 0;
}
2021/7/15 19:50
加载中...