Help!30分代码
查看原帖
Help!30分代码
670154
sunxhx楼主2022/3/21 11:05
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4;
struct node {
	double x;
	double y;
	double z;
} a[N];
int vis[N], n, h, r, t;
queue<node> q;
double dist(node a, node b) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	double dz = a.z - b.z;
	double ans = sqrt(dx * dx + dy * dy + dz * dz);
	return ans;
}
bool bfs() {
	while (!q.empty()) {
		if (q.front().z + r >= h)
			return true;
		node now = q.front();
		q.pop();
		for (int i = 1; i <= n; i++) {
			if (r * 2 >= dist(now, a[i]) && !vis[i]) {
				q.push(a[i]);
				vis[i] = 1;
				if (q.front().z + r >= h) 
					return true;
			}
		}
	}
	return false;
}
int main () {
	cin >> t;
	while (t--) {
		cin >> n >> h >> r;
		for (int i = 1; i <= n; i++) 
			cin >> a[i].x >> a[i].y >> a[i].z;
		memset(vis, false, sizeof(vis));
		for (int i = 1; i <= n; i++) 
			if (a[i].z - r <= 0) {
				q.push(a[i]);
				vis[i] = 1;
			}
		if (bfs()) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
	return 0;
}
2022/3/21 11:05
加载中...