记录编号	475897	评测结果	WWWWWWWWTT
题目名称	[NOIP 2017]奶酪	最终得分	0
用户昵称	+1s	是否通过	未通过
代码语言	C++	运行时间	2.685 s
提交时间	2017-11-19 15:35:09	内存使用	4.93 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
int T,n,h,r,arc[1100][1100],vsd[1100],end[1100],can=0;
struct
{
	int x,y,z;
}pnt[1100];
int xiangjiao(int i,int j)
{
	double g=r*2;
	double dis=sqrt((pnt[i].x-pnt[j].x)*(pnt[i].x-pnt[j].x)+(pnt[i].y-pnt[j].y)*(pnt[i].y-pnt[j].y)+(pnt[i].z-pnt[j].z)*(pnt[i].z-pnt[j].z));
	return dis<=g;
}
void dfs(int nod)
{
	if(can==1)return;
	if(end[nod]==1)
	{
		can=1;
		return;
	}
	vsd[nod]=1;
	for(int i=1;i<=n;i++)
	{
		if(vsd[i]==0&&arc[nod][i])
		{
			vsd[i]=1;
			dfs(i);
		}
	}
}
int main()
{
	freopen("2017cheese.in","r",stdin);
	freopen("2017cheese.out","w",stdout);
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
		can=0;
		scanf("%d %d %d",&n,&h,&r);
		memset(pnt,0,sizeof(pnt));
		memset(arc,0,sizeof(arc));
		memset(vsd,0,sizeof(vsd));
		for(int i=1;i<=n;i++)
		{
			scanf("%d %d %d",&pnt[i].x,&pnt[i].y,&pnt[i].z);
		}
		for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		if(xiangjiao(i,j))
		{
			arc[i][j]=1;
			arc[j][i]=1;
		}
		for(int i=1;i<=n;i++)
		{
			if(pnt[i].z+r>=h)
			{
				end[i]=1;
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(can==1)
			break;
			if(pnt[i].z-r<=0)
			{
				dfs(i);
			}
		}
		if(can==1)printf("Yes\n");
		else printf("No\n");
	} 
	return 0;
}