记录编号	476707	评测结果	AAAAAAAAAA
题目名称	[NOIP 2017]奶酪	最终得分	100
用户昵称	nonamenotitle	是否通过	通过
代码语言	C++	运行时间	0.815 s
提交时间	2017-11-26 18:27:51	内存使用	15.78 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cctype>
#include <climits>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int ,int > pii;
typedef pair<int ,ll> pil;
typedef pair<ll,int > pli;
typedef pair<ll,ll> pll;
#define MP make_pair
#define fir first
#define sec second
inline int readInt()
{
	char c;int tmp=0,x=1;c=getchar();
	while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
	while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
	return tmp*x;
}
inline ll readLL()
{
	char c;ll tmp=0,x=1;c=getchar();
	while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
	while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
	return tmp*x;
}
const double eps=1e-6;
struct ball{
	double x,y,z;
	ball(double x=0,double y=0,double z=0): x(x),y(y),z(z) {}
};
const int maxn=1000+5;
ball b[maxn];
int T,n;
double h,R,W[maxn*maxn];
int ST,ED,hd[maxn<<1],eg[maxn*maxn],nxt[maxn*maxn],tot=0;
void addedge(int u,int v,double cost)
{
	eg[++tot]=v;nxt[tot]=hd[u];W[tot]=cost;hd[u]=tot;
	eg[++tot]=u;nxt[tot]=hd[v];W[tot]=cost;hd[v]=tot;
}
double pf(double x){return x*x;}
double Dis(int A,int B)
{
	return sqrt(pf(b[A].x-b[B].x)+pf(b[A].y-b[B].y)+pf(b[A].z-b[B].z));
}
bool inque[maxn<<1];
int q[maxn<<1];
double dis[maxn<<1];
void spfa(int st,int ed)
{
	int N=n+2;
	int head=0,tail=0;
	memset(inque,0,sizeof(inque));
	inque[st]=true;q[head]=st;
	for(int i=0;i<maxn;++i) dis[i]=1e60;
	dis[st]=0;
	while(head<=tail){
		int v=q[head%N];head++;
		for(int i=hd[v];~i;i=nxt[i]){
			int u=eg[i];
			if(dis[v]!=1e60 && dis[u]>dis[v]+W[i]){
				dis[u]=dis[v]+W[i];
				if(!inque[u]){
					tail++;q[tail%N]=u;
				}
			}
		}
	}
}
int main()
{
	freopen("2017cheese.in","r",stdin);
	freopen("2017cheese.out","w",stdout);
	scanf("%d",&T);
	for(int z=0;z<T;++z)
	{
		memset(hd,-1,sizeof(hd));
		memset(nxt,-1,sizeof(nxt));
		for(int j=0;j<maxn*maxn;++j) W[j]=0;
		tot=0;
		scanf("%d%lf%lf",&n,&h,&R);
		ST=0,ED=n+1;
		for(int i=1;i<=n;++i) scanf("%lf%lf%lf",&b[i].x,&b[i].y,&b[i].z);
		for(int i=1;i<=n;++i){
			if(b[i].z<=R) addedge(ST,i,b[i].z);
		}
		double tmp=0;
		for(int i=1;i<=n;++i){
			for(int j=i+1;j<=n;++j){
				tmp=Dis(i,j);
			//	printf("tmp=%f\n",tmp);
			//	printf("2*R=%f\n",2*R);
				if(tmp<=2*R) addedge(i,j,tmp);
			}
		}
		for(int i=1;i<=n;++i){
			if(b[i].z+R>=h) addedge(i,ED,h-b[i].z);
		}
	/*	for(int i=ST;i<=ED;++i){
			printf("from %d:\n",i);
			for(int j=hd[i];~j;j=nxt[j]){
				printf("to %d cost %f\n",eg[j],W[j]);
			}puts("");
		}*/
		spfa(ST,ED);
		if(dis[ED]!=1e60) printf("Yes\n");
		else printf("No\n");
		//assert(0);
	}
	return 0;
}