样例都过不去
查看原帖
样例都过不去
243672
する楼主2020/8/2 21:34
#include<bits/stdc++.h>
using namespace std;
int father[10005];
int find(int n)
{
	if(father[n]==n)
	{
		return n;
	}
	return father[n]=find(father[n]);
}
void u(int x,int y)
{
	int a=find(x);
	int b=find(y);
	if(a!=b)
	{
		father[b]=a;
	}
	return ;
}
double len(int x1,int y1,int z1,int x2,int y2,int z2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
void help()
{
	int n,h,r,x[10005],y[10005],z[10005];
	cin>>n>>h>>r;
	for(int i=0;i<=n+1;i++)
	{
		father[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i]>>z[i];
		if(len(x[i],y[i],z[i],0,y[i],z[i])<=r)
		{
			u(i,0);
		}
		if(len(x[i],y[i],z[i],h+1,y[i],z[i])<=r)
		{
			u(i,h+1);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j)
			{
				if(len(x[i],y[i],z[i],x[j],y[j],z[j])<=r+r)
				{
					u(i,j);
				}
			}
		}
	}
	if(find(0)==find(h+1))
	{
		cout<<"YES"<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
}
int main()
{
	int t;
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		help();
	} 
	return 0;
}
2020/8/2 21:34
加载中...