UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#205964#892. 奶酪wyz_100577ms1416kbC++111.2kb2024-07-20 18:21:052024-07-20 20:09:07

answer

#include<bits/stdc++.h>
using namespace std;

#define y1 yy

int t;

inline double dis(int x1,int y1,int z1,int x2,int y2,int z2){
	return sqrt(pow(x1-x2,2)+pow(y1-y2,2)+pow(z1-z2,2));
}
bool bfs(const int& s,const int& e,const int& n,const vector<int>*g){
	bool vis[n+5];
	memset(vis,0,sizeof vis);
	vis[s] = 1;
	queue<int>q;
	q.push(s);
	
	while(q.size()){
		if(q.front() == e)
			return 1;
		
		for(auto& p : g[q.front()]){
			if(!vis[p])
				vis[p] = 1, q.push(p);
		}
		
		q.pop();
	}
	return 0;
}

inline bool solve(){
	int n,h,r;
	cin >> n >> h >> r;
	int a[n+5][3];
	vector<int>g[n+5];
	for(int i = 1; i <= n; i++){
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		if(a[i][2] <= r)
			g[0].push_back(i);
		if(a[i][2] + r >= h)
			g[i].push_back(n+1);
	}
	int r2 = r << 1;
	for(int i = 1; i < n; i++){
		for(int j = i+1; j <= n; j++){
			if(dis(a[i][0],a[i][1],a[i][2],a[j][0],a[j][1],a[j][2]) <= r2)
				g[i].push_back(j), g[j].push_back(i);
		}
	}
	return bfs(0,n+1,n,g);
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin >> t;
	while(t--)
		cout << (solve() ? "Yes\n" : "No\n");
	
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 122ms
memory: 1360kb

input:

20
2 5100500 1275250
0 0 1275250
1 50500 3825250
1000 94972653 9368205
-99057506 56850186 89511048
8...

output:

No
Yes
Yes
No
No
Yes
Yes
No
No
No
No
No
Yes
No
No
Yes
No
No
No
Yes

result:

ok 20 lines

Test #2:

score: 10
Accepted
time: 1ms
memory: 1240kb

input:

20
8 8535 7995
-2894 -344 102
-368 -8400 3331
6732 4330 3462
9929 9940 430
205 -2958 1596
-4440 432 ...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
Yes
Yes
No
Yes

result:

ok 20 lines

Test #3:

score: 10
Accepted
time: 0ms
memory: 1236kb

input:

6
2 1000 250
0 0 250
0 0 751
2 1000 400
400 750 5
840 716 718
3 2000 600
328 1454 1005
114 736 1503
...

output:

No
No
No
No
No
Yes

result:

ok 6 lines

Test #4:

score: 10
Accepted
time: 0ms
memory: 1224kb

input:

20
1 1000 563
79 29 664
1 1000 642
934 972 673
1 1000 500
356 256 76
1 1000 498
252 32 672
1 1000 99...

output:

No
No
No
No
Yes
Yes
No
No
No
No
No
No
No
Yes
No
Yes
Yes
Yes
No
Yes

result:

ok 20 lines

Test #5:

score: 10
Accepted
time: 0ms
memory: 1216kb

input:

5
1 100 60
70 27 88
1 100 75
80 39 34
1 100 50
605 563 50
1 200 160
120 176 40
1 200 10
50 47 84

output:

No
Yes
Yes
Yes
No

result:

ok 5 lines

Test #6:

score: 10
Accepted
time: 33ms
memory: 1356kb

input:

5
1000 4928 258
-7744 9886 3739
2325 7894 4178
5520 6510 3780
-1886 -5269 142
1301 8784 2122
-6921 4...

output:

No
Yes
No
Yes
Yes

result:

ok 5 lines

Test #7:

score: 10
Accepted
time: 63ms
memory: 1352kb

input:

10
1000 5108 828
-976 -7844 5051
7232 -8508 1564
-6275 6927 3465
-6018 7088 1644
2672 9265 1936
7818...

output:

Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes

result:

ok 10 lines

Test #8:

score: 10
Accepted
time: 127ms
memory: 1416kb

input:

20
1000 5131 531
-8405 125 4237
9480 3440 2981
-8310 8496 4984
-9910 -5463 2701
-258 -5683 3899
2792...

output:

Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
No

result:

ok 20 lines

Test #9:

score: 10
Accepted
time: 110ms
memory: 1372kb

input:

20
2 5202 1301
0 0 1301
102 0 3901
2 5202 1301
0 0 1301
102 1 3901
1000 7236 649
-7117 -6085 4914
74...

output:

Yes
No
Yes
Yes
Yes
No
Yes
No
No
No
Yes
No
No
No
Yes
Yes
Yes
No
Yes
No

result:

ok 20 lines

Test #10:

score: 10
Accepted
time: 121ms
memory: 1384kb

input:

20
2 5100500 1275250
0 0 1275250
0 50500 3825250
1000 95100603 1624126
-83359625 75545594 84471552
-...

output:

Yes
No
No
No
Yes
No
Yes
Yes
Yes
No
No
No
Yes
No
No
No
No
No
No
No

result:

ok 20 lines