提交记录 12927


用户 题目 状态 得分 用时 内存 语言 代码长度
lrw04 noip17d. 【NOIP2017】奶酪 Accepted 100 24.755 ms 72 KB C++11 1.45 KB
提交时间 评测时间
2020-07-04 23:12:01 2020-08-01 03:01:30
#include <iostream>
using namespace std;
typedef long long ll;

struct Sphere {
	ll x, y, z;
	Sphere(ll x=0, ll y=0, ll z=0): x(x), y(y), z(z) {}
};
#define MAXN 1050
Sphere sp[MAXN];
ll n, h, r;
int fa[MAXN];

ll sq(ll s) {
	return s * s;
}

ll distsq(Sphere s, Sphere p) {
	return sq(s.x - p.x) + sq(s.y - p.y) + sq(s.z - p.z);
}

bool intersect(Sphere s, Sphere p) {
	return distsq(s, p) <= 4 * r * r;
}

void ufsinit() {
	for (int i = 1; i <= n + 2; i++) fa[i] = i;
}

int ufsfind(int x) {
	if (fa[x] == x) return x;
	return fa[x] = ufsfind(fa[x]);
}

bool ufspr(int a, int b) {
	return ufsfind(a) == ufsfind(b);
}

void ufsmerge(int a, int b) {
	if (!ufspr(a, b))
		fa[ufsfind(a)] = fa[ufsfind(b)];
}

// Node 1 is bottom, Node n + 2 is top
void solveone() {
	cin >> n >> h >> r;
	ufsinit();
	for (int i = 2; i < n + 2; i++) {
		cin >> sp[i].x >> sp[i].y >> sp[i].z;
		if (sp[i].z <= r) {
			ufsmerge(1, i); 
//			cout << i << " bottom" << endl; 
		}
		if (sp[i].z + r >= h) { 
			ufsmerge(i, n + 2); 
//			cout << i << " top" << endl; 
		}
	}
	
	for (int i = 2; i < n + 1; i++)
	for (int j = i + 1; j < n + 2; j++) {
		if (intersect(sp[i], sp[j]))
			ufsmerge(i, j);
//		cout << i << " " << j << " " << intersect(sp[i], sp[j]) << endl;
	}
	
//	for (int i = 1; i <= n + 2; i++) cout << fa[i] << " "; cout << endl;
	if (ufsfind(1) == ufsfind(n + 2)) cout << "Yes" << endl;
	else cout << "No" << endl;
}

int main() {
	int z;
	cin >> z;
	while (z--) {
		solveone();
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #143.99 us64 KBAcceptedScore: 10

Testcase #274.49 us64 KBAcceptedScore: 10

Testcase #367.62 us64 KBAcceptedScore: 10

Testcase #4127.81 us64 KBAcceptedScore: 10

Testcase #55.61 ms72 KBAcceptedScore: 10

Testcase #611.205 ms68 KBAcceptedScore: 10

Testcase #722.137 ms72 KBAcceptedScore: 10

Testcase #819.904 ms68 KBAcceptedScore: 10

Testcase #924.688 ms68 KBAcceptedScore: 10

Testcase #1024.755 ms68 KBAcceptedScore: 10


Judge Duck Online | 评测鸭在线
Server Time: 2020-08-05 15:15:02 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用