NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #205960 | #892. 奶酪 | Allen123456hello | 100 | 1334ms | 1704kb | C++11 | 1.3kb | 2024-07-20 18:19:04 | 2024-07-20 20:08:26 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
bool vis[1005];
struct point{
long double x,y,z;
}arr[1005];
struct edge{
int u,v,nxt;
}e[2000005];
int head[1005],pos=1;
void add_edge(int u,int v){
e[++pos]={u,v,head[u]};
head[u]=pos;
}
long double dis(point a,point b){
return __builtin_sqrtl(((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y))+((a.z-b.z)*(a.z-b.z)));
}
void dfs(int u){
vis[u]=1;
for (int i=head[u];i;i=e[i].nxt){
if (!vis[e[i].v]){dfs(e[i].v);}
}
return;
}
void work(){
memset(vis,0,sizeof vis);
memset(head,0,sizeof head);
for (int i=0;i<=1003;++i){e[i].u=e[i].v=e[i].nxt=0;}
pos=1;
int n;long double h,r;
scanf("%d%Lf%Lf",&n,&h,&r);
for (int i=1;i<=n;++i){
scanf("%Lf%Lf%Lf",&arr[i].x,&arr[i].y,&arr[i].z);
}
for (int i=1;i<=n;++i){
for (int j=1;j<=n;++j){
if (i==j){continue;}
if (dis(arr[i],arr[j])<=(r+r)){add_edge(i,j);add_edge(j,i);}
}
}
for (int i=1;i<=n;++i){
if ((arr[i].z+r)>=h){add_edge(i,n+2);add_edge(n+2,i);}
if ((arr[i].z-r)<=0){add_edge(i,n+1);add_edge(n+1,i);}
}
dfs(n+1);
puts(vis[n+2]?"Yes":"No");
}
int main(){
int T;
scanf("%d",&T);
++T;while (--T){work();}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 155ms
memory: 1480kb
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: 1232kb
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: 1236kb
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: 1232kb
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: 44ms
memory: 1444kb
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: 173ms
memory: 1468kb
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: 340ms
memory: 1704kb
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: 305ms
memory: 1512kb
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: 316ms
memory: 1556kb
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
