Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
cheese
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 1020
using namespace std;
long long n, h, d;
long long x[N], y[N], z[N];
int q[N], l, r;
bool u[N];
unsigned long long Distance(int a, int b)
{
return (unsigned long long)((x[a] - x[b]) * (x[a] - x[b])) + (unsigned long long)((y[a] - y[b]) * (y[a] - y[b])) + (unsigned long long)((z[a] - z[b]) * (z[a] - z[b]));
}
bool BFS(void)
{
int i, j;
memset(u, false, sizeof(u));
for(i = l = 0, r = -1;i < n;i ++)
if(z[i] <= d)
{
q[++ r] = i;
u[i] = true;
//printf("IN %d\n",i);
if(z[i] + d >= h)
return true;
}
for(;l <= r;l ++)
for(i = 0;i < n;i ++)
{
//printf("%d -> %d : %d\n",q[l],i,Distance(q[l], i));
if(Distance(q[l], i) <= (unsigned long long)d * d * 4 && !u[i])
{
//printf("GET %d\n",i);
u[i] = true;
q[++ r] = i;
if(z[i] + d >= h)
return true;
}
}
return false;
}
void Solve(void)
{
int i;
scanf("%lld %lld %lld", &n, &h, &d);
for(i = 0;i < n;i ++)
scanf("%lld %lld %lld", &x[i], &y[i], &z[i]);
puts(BFS() ? "Yes" : "No");
return;
}
int main() //cheese.cpp
{
int t;
freopen("cheese.in" , "r", stdin );
freopen("cheese.out", "w", stdout);
scanf("%d", &t);
while(t --)
Solve();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.