题目描述
blablabla
样例
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1005;
int xs[N],ys[N],zs[N];
bool co[N][N],vis[N];
double dist(int x,int y){
double dx = xs[x] - xs[y],dy = ys[x] - ys[y],dz =zs[x] - zs[y];
return sqrt(dx * dx + dy * dy + dz * dz);
}
bool dfs(int now,int n){
vis[now] = 1;
if(now == 1)
return 1;
for(int i = 1; i <= n+1; i ++ ){
if(co[now][i] && !vis[i] && dfs(i,n))
return 1;
}
return 0;
}
int main()
{
int t;
scanf("%d", &t);
while(t -- ){
int n,h,r;
scanf("%d%d%d", &n, &h,&r);
memset(co, 0, sizeof co);
for(int i = 2; i <= n + 1; i ++ ){
scanf("%d%d%d", &xs[i], &ys[i],&zs[i]);
for(int j = 2; j < i; j ++ ){
if(dist(j,i) <= r * 2){
co[i][j] = co[j][i] = 1;
}
}
if(zs[i] <= r){
co[0][i] = 1;
}
if(h - zs[i] <= r){
co[i][1] = 1;
}
}
memset(vis, 0, sizeof vis);
puts(dfs(0,n) ?"Yes" : "No");
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla