【NOIP2017】奶酪 题解
Day2T1，普及/提高-
题目链接
这是一篇原始文章，不保证内容的正确性
核心思路
用一个结构体point封装点。
从1到n找到所有的与下底面相连的洞，即abs(a[i].z)<=r。
从它开始dfs一步一步向与它所连的洞dist(a[i],a[x])>2*r搜索。
如果到达一个洞可以到达上表面，即a[x].z+r>=h，就找到答案了。
如果全部遍历了一遍都还没找到就可以确定不能到达了。
坐标距离公式，记得要double。
1
2
3
| double dist(point a,point b){
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2));
}
|
一个没有任何技术含量的dfs。
1
2
3
4
5
6
7
8
9
10
11
| void dfs(long long x){
if(arr||x>n)return;
if(a[x].z+r>=h){arr=1;return;}
for(long long i=1;i<=n;i++){
if(have[i]||dist(a[i],a[x])>2*r)continue;
have[i]=1;
dfs(i);
}
}
|
主函数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int main(){
double H=read();
for(double i=1;i<=H;i++){
arr=0;
s=0;
n=read(),h=read(),r=read();
for(int i=1;i<=n;i++)have[i]=0;
for(long long i=1;i<=n;i++){
a[i].x=read();
a[i].y=read();
a[i].z=read();
}
for(long long i=1;i<=n;i++)
if(abs(a[i].z)<=r){
have[i]=1;
dfs(i);
for(int i=1;i<=n;i++)have[i]=0;
}
if(arr)cout<<"Yes \n";
else cout<<"No \n";
}
}
|
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
#define MAXN 1000+10
#define MAXM 10000+10
using namespace std;
double read(){
double x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct point{
double x,y,z;
}a[MAXN];
double dist(point a,point b){
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)+pow(a.z-b.z,2));
}
bool have[MAXM],arr;
long long n,h,r;
int s=0;
void dfs(long long x){
if(arr||x>n)return;
if(a[x].z+r>=h){arr=1;return;}
for(long long i=1;i<=n;i++){
if(have[i]||dist(a[i],a[x])>2*r)continue;
have[i]=1;
dfs(i);
}
}
int main(){
double H=read();
for(double i=1;i<=H;i++){
arr=0;
s=0;
n=read(),h=read(),r=read();
for(int i=1;i<=n;i++)have[i]=0;
for(long long i=1;i<=n;i++){
a[i].x=read();
a[i].y=read();
a[i].z=read();
}
for(long long i=1;i<=n;i++)
if(abs(a[i].z)<=r){
have[i]=1;
dfs(i);
for(int i=1;i<=n;i++)have[i]=0;
}
if(arr)cout<<"Yes \n";
else cout<<"No \n";
}
return 0;
}
|
