P3958 NOIP2017 奶酪 洛谷

WWX

https://www.luogu.org/problemnew/show/P3958
题目描述

现有一块大奶酪，它的高度为 hh ，它的长度和宽度我们可以认为是无限大的，奶酪 中间有许多 半径相同 的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中， 奶酪的下表面为 z = 0z=0 ，奶酪的上表面为 z = hz=h 。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐 标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别 地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果 一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在 不破坏奶酪 的情况下，能否利用已有的空洞跑 到奶酪的上表面去?

每个输入文件包含多组数据。

的第一行，包含一个正整数 T ，代表该输入文件中所含的数据组数。

接下来是 T 组数据，每组数据的格式如下： 第一行包含三个正整数 n,h和 r ，两个数之间以一个空格分开，分别代表奶酪中空 洞的数量，奶酪的高度和空洞的半径。

接下来的 n 行，每行包含三个整数 x,y,z ，两个数之间以一个空格分开，表示空 洞球心坐标为 (x,y,z) 。

输出格式：

T行，分别对应 T 组数据的答案，如果在第 i组数据中，Jerry 能从下 表面跑到上表面，则输出Yes，如果不能，则输出No （均不包含引号）。

WWX

并查集水题，直接上代码

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cstring>
   
4. #include <cstdio>
   
5. #define ull unsigned long long
   
6. using namespace std;
   
7. int t,n,tot;
   
8. int head[1010];
   
9. bool vis[1010];
   
10. long long h,r;
    
11. struct Node
    
12. {
    
13.     long long x,y,z;
    
14. } p[1010];
    
15. ull get_dis(const Node &a,const Node &b)
    
16. {
    
17.     return (ull)((a.x-b.x)*(a.x-b.x))+(ull)((a.y-b.y)*(a.y-b.y))+(ull)((a.z-b.z)*(a.z-b.z));
    
18. }
    
19. struct Map
    
20. {
    
21.     int r,next;
    
22. } line[1001010];
    
23. void add(int x,int y)
    
24. {
    
25.     tot++;
    
26.     line[tot].r=y;
    
27.     line[tot].next=head[x];
    
28.     head[x]=tot;
    
29. }
    
30. void dfs(int x)
    
31. {
    
32.     vis[x]=true;
    
33.     for(int i=head[x]; i; i=line[i].next)
    
34.         if(!vis[line[i].r])
    
35.             dfs(line[i].r);
    
36. }
    
37. inline int read()
    
38. {
    
39.     int x=0;
    
40.     bool f=0;
    
41.     char ch=getchar();
    
42.     while(ch<'0'||ch>'9')
    
43.     {
    
44.         if(ch=='-')
    
45.             f=1;
    
46.         ch=getchar();
    
47.     }
    
48.     while(ch>='0'&&ch<='9')
    
49.     {
    
50.         x=x*10+ch-'0';
    
51.         ch=getchar();
    
52.     }
    
53.     return f?-x:x;
    
54. }
    
55. int main()
    
56. {
    
57.     t=read();
    
58.     while(t--)
    
59.     {
    
60.         tot=0;
    
61.         memset(vis,0,sizeof(vis));
    
62.         memset(head,0,sizeof(head));
    
63.         n=read(),h=read(),r=read();
    
64.         for(int i=1; i<=n; i++)
    
65.         {
    
66.             p[i].x=read(),p[i].y=read(),p[i].z=read();
    
67.             if(p[i].z-r<=0)
    
68.                 add(0,i);
    
69.             if(p[i].z+r>=h)
    
70.                 add(i,n+1);
    
71.         }
    
72.         for(register int i=1; i<=n; i++)
    
73.             for(register int j=i+1; j<=n; j++)
    
74.                 if(get_dis(p[i],p[j])<=(ull)((r+r)*(r+r)))
    
75.                     add(i,j),add(j,i);
    
76.         dfs(0);
    
77.         if(vis[n+1])
    
78.             puts("Yes");
    
79.         else puts("No");
    
80.     }
    
81.     return 0;
    
82. }
    

复制代码

吴语林

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <algorithm>
   
7. using namespace std;
   
8. long long t,n,h,r,a[1003][4]= {0};
   
9. int lian[1003][1003]= {0},ru[1003]= {0},e=0,book[1003]= {0},la=0;
   
10. void dfs(int ha)
    
11. {
    
12.         if(e)
    
13.                 return;
    
14.         for(int i=1; i<=lian[ha][0]; i++)
    
15.         {
    
16.                 if(lian[ha][i]==2500)
    
17.                 {
    
18.                         e=1;
    
19.                         return;
    
20.                 }
    
21.                 else
    
22.                 {
    
23.                         if(e)
    
24.                                 return;
    
25.                         if(book[lian[ha][i]]==0)
    
26.                         {
    
27.                                 book[lian[ha][i]]=1;
    
28.                                 dfs(lian[ha][i]);
    
29.                         }
    
30.                 }
    
31.         }
    
32. }
    
33. int main()
    
34. {
    
35.         scanf("%lld",&t);
    
36.         while(t--)
    
37.         {
    
38.                 memset(book,0,sizeof(book));
    
39.                 memset(lian,0,sizeof(lian));
    
40.                 memset(ru,0,sizeof(ru));
    
41.                 memset(a,0,sizeof(a));
    
42.                 e=0,la=0;
    
43.                 scanf("%lld%lld%lld",&n,&h,&r);
    
44.                 for(long long i=1; i<=n; i++)
    
45.                 {
    
46.                         scanf("%lld%lld%lld",&a[i][1],&a[i][2],&a[i][3]);
    
47.                         if(abs(a[i][3])<=r&&abs(a[i][3])>=h-r)
    
48.                                 la=1;
    
49.                         if(abs(a[i][3])<=r)
    
50.                         {
    
51.                                 ru[0]++;
    
52.                                 ru[ru[0]]=i;
    
53.                         }
    
54.                         if(abs(a[i][3])>=h-r)
    
55.                         {
    
56.                                 lian[i][0]++;
    
57.                                 lian[i][lian[i][0]]=2500;
    
58.                                 e=1;
    
59.                         }
    
60.                         for(long long j=i-1; j>=1; j--)
    
61.                         {
    
62.                                 if(sqrt((a[i][1]-a[j][1])*(a[i][1]-a[j][1])+(a[i][2]-a[j][2])*(a[i][2]-a[j][2])+(a[i][3]-a[j][3])*(a[i][3]-a[j][3]))<=(2*r))
    
63.                                 {
    
64.                                         lian[i][0]++;
    
65.                                         lian[i][lian[i][0]]=j;
    
66.                                         lian[j][0]++;
    
67.                                         lian[j][lian[j][0]]=i;
    
68.                                 }
    
69.                         }
    
70.                 }
    
71.                 if(la==1)
    
72.                 {
    
73.                         printf("Yes\n");
    
74.                         continue;
    
75.                 }
    
76.                 if(e==0||ru[0]==0)
    
77.                 {
    
78.                         printf("No\n");
    
79.                         continue;
    
80.                 }
    
81.                 e=0;
    
82.                 for(int i=1; i<=ru[0]; i++)
    
83.                 {
    
84.                         book[ru[i]]=1;
    
85.                         dfs(ru[i]);
    
86.                         if(e)
    
87.                                 break;
    
88.                 }
    
89.                 if(e)
    
90.                         printf("Yes\n");
    
91.                 else
    
92.                         printf("No\n");
    
93.         }
    
94.         return 0;
    
95. }

复制代码

zhwang

1. #include<cstdio>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int f[1001+1][1001+1];
   
5. int t,n,h,r;
   
6. int x[1001],y[1001],z[1001];
   
7. const int INF=999999999;
   
8. struct node
   
9. {
   
10.         int x;
    
11.         int y;
    
12.         int z;
    
13. }dong[1001];
    
14. int cmp(node a,node b)
    
15. {
    
16.         if(a.z<b.z)
    
17.         {
    
18.                 return 1;
    
19.         }
    
20.         else
    
21.         {
    
22.                 return 0;
    
23.         }
    
24. }
    
25. int main()
    
26. {
    
27.         scanf("%d",&t);
    
28.         while(t--)
    
29.         {
    
30.                 scanf("%d%d%d",&n,&h,&r);
    
31.                 for(int i=1;i<=n;i++)
    
32.                 {
    
33.                         dong[i].x=dong[i].y=dong[i].z;
    
34.                 }
    
35.                 for(int i=1;i<=n;i++)
    
36.                 {
    
37.                         scanf("%d%d%d",&dong[i].x,&dong[i].y,&dong[i].z);
    
38.                 }
    
39.                 sort(dong+1,dong+1+n,cmp);
    
40.                 if(dong[1].z-r>0||dong[n].z+r<h)
    
41.                 {
    
42.                         printf("no\n");
    
43.                         continue;
    
44.                 }
    
45.                 for(int i=0;i<=n+1;i++)
    
46.                 {
    
47.                         for(int j=0;j<=n+1;j++)
    
48.                         {
    
49.                                 if(i==j)
    
50.                                 {
    
51.                                         f[i][j]=0;
    
52.                                 }
    
53.                                 else
    
54.                                 {
    
55.                                         f[i][j]=INF;
    
56.                                 }
    
57.                         }
    
58.                 }
    
59.                 //printf("%d  ",f[0][n+1]);
    
60.                 for(int i=1;i<=n;i++)
    
61.                 {
    
62.                         if(dong[i].z-r<=0)
    
63.                         {
    
64.                                 f[0][i]=1;
    
65.                                 f[i][0]=1;
    
66.                         }
    
67.                         if(dong[i].z+r>=h)
    
68.                         {
    
69.                                 f[n+1][i]=1;
    
70.                                 f[i][n+1]=1;
    
71.                         }
    
72.                 }
    
73.                 for(int i=1;i<=n;i++)
    
74.                 {
    
75.                         for(int j=i+1;j<=n;j++)
    
76.                         {
    
77.                                 if(r*2*2*r>=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])+(z[j]-z[i])*(z[j]-z[i]))
    
78.                                 {
    
79.                                         f[i][j]=f[j][i]=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])+(z[j]-z[i])*(z[j]-z[i]);
    
80.                                 }
    
81.                         }
    
82.                 }
    
83.                 //floyd大法好
    
84.                 for(int k=0;k<=n+1;k++)
    
85.                 {
    
86.                         for(int i=0;i<=n+1;i++)
    
87.                         {
    
88.                                 for(int j=0;j<=n+1;j++)
    
89.                                 {
    
90.                                         if(f[i][j]>f[i][k]+f[k][j])
    
91.                                         {
    
92.                                                 f[i][j]=f[i][k]+f[k][j];
    
93.                                         }
    
94.                                 }
    
95.                         }
    
96.                 }
    
97.                 if(f[0][n+1]>=INF)
    
98.                 {
    
99.                         printf("No\n");
    
100.                 }
     
101.                 else
     
102.                 {
     
103.                         printf("Yes\n");
     
104.                 }
     
105.         }
     
106.         return 0;
     
107. }

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. int t,par[1001];
   
5. int n,h,f1[1001],f2[1001],n1,n2;
   
6. bool b;
   
7. typedef long long ll;
   
8. ll r;
   
9. struct hole
   
10. {
    
11.     ll x,y,z;
    
12. }a[1010];
    
13. int find(int x)
    
14. {
    
15.     if (par[par[x]]!=par[x]) par[x]=par[par[x]];
    
16.     return par[x];
    
17. }
    
18. double dis(ll x,ll y,ll z,ll x1,ll y1,ll z1)
    
19. {
    
20.     return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1)+(z-z1)*(z-z1));
    
21. }
    
22. int main()
    
23. {
    
24.     cin>>t;
    
25.     while(t--)
    
26.     {
    
27.         cin>>n>>h>>r;
    
28.         b=true;
    
29.         n1=n2=0;
    
30.         for(int i=1;i<=n;i++)par[i]=i;
    
31.         for(int i=1;i<=n;i++)
    
32.         {
    
33.             cin>>a[i].x>>a[i].y>>a[i].z;
    
34.             if(a[i].z+r>=h)f1[++n1]=i;
    
35.             if(a[i].z-r<=0)f2[++n2]=i;
    
36.             for(int j=1;j<=i;j++)
    
37.                 if(dis(a[i].x,a[i].y,a[i].z,a[j].x,a[j].y,a[j].z)<=2*r)
    
38.             {
    
39.                 int a1=find(i);
    
40.                 int a2=find(j);
    
41.                 if (a1!=a2)par[a1]=a2;
    
42.             }
    
43.         }
    
44.         for(int i=1;i<=n1&&b;i++)
    
45.             for(int j=1;j<=n2&&b;j++)
    
46.                 if(find(f1[i])==find(f2[j]))b=false;
    
47.         if(!b)cout<<"Yes"<<endl;
    
48.         else cout<<"No"<<endl;
    
49.     }
    
50.     return 0;
    
51. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. long long top[1001],bottom[1001],count1,count2,x[1001],y[1001],z[1001],father[1001];
   
3. long long n,h,r;
   
4. int getfather(int x)
   
5. {
   
6.         if(x==father[x])
   
7.                 return x;
   
8.         return father[x]=getfather(father[x]);
   
9. }
   
10. bool judge(int i,int j)
    
11. {
    
12.         long long dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]);
    
13.         long long d=4*r*r;
    
14.         if(dis<=d)
    
15.                 return 1;
    
16.         return 0;
    
17. }
    
18. int main()
    
19. {
    
20.         int t;
    
21.         scanf("%d",&t);
    
22.         for(int o=1;o<=t;o++)
    
23.         {
    
24.                 scanf("%lld%lld%lld",&n,&h,&r);
    
25.                 count1=count2=0;
    
26.                 for(int i=1;i<=n;i++)
    
27.                         top[i]=bottom[i]=0;
    
28.                 for(int i=1;i<=n;i++)
    
29.                         father[i]=i;
    
30.                 for(int i=1;i<=n;i++)
    
31.                 {
    
32.                         scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);
    
33.                         if(z[i]<=r)
    
34.                                 bottom[++count1]=i;
    
35.                         if(z[i]>=h-r)
    
36.                                 top[++count2]=i;
    
37.                         for(int j=1;j<=i;j++)
    
38.                                 if(judge(i,j) && getfather(i)!=getfather(j))
    
39.                                         father[getfather(i)]=getfather(j);
    
40.                 }
    
41.                 int flag=0;
    
42.                 for(int i=1;i<=count1;i++)
    
43.                 {
    
44.                         for(int j=1;j<=count2;j++)
    
45.                                 if(getfather(bottom[i])==getfather(top[j]))
    
46.                                 {
    
47.                                         flag=1;
    
48.                                         break;
    
49.                                 }
    
50.                         if(flag)
    
51.                                 break;
    
52.                 }
    
53.                 if(flag)
    
54.                         printf("Yes\n");
    
55.                 else
    
56.                         printf("No\n");
    
57.         }
    
58.         return 0;
    
59. }

复制代码

张笑宇

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. const int mx=101000;
   
5. int t,n,par[mx];
   
6. double r;
   
7. long long x[mx],y[mx],z[mx],h;
   
8. int i,j,k;
   
9. int sunder,shead,under_[mx],head_[mx];
   
10. int getpar(int a)
    
11. {
    
12.         if (a!=par[a])
    
13.                 par[a]=getpar(par[a]);
    
14.         return par[a];
    
15. }
    
16. int main()
    
17. {
    
18.         cin>>t;
    
19.         while (t--)
    
20.         {
    
21.                 cin>>n>>h>>r;
    
22.                 for (i=1;i<=n;i++) par[i]=i;
    
23.                 shead=0,sunder=0;
    
24.                 for (i=1;i<=n;i++)
    
25.                 {
    
26.                         cin>>x[i]>>y[i]>>z[i];
    
27.                         if (z[i]+r>=h)///与顶上连接
    
28.                         {
    
29.                                 shead++;
    
30.                                 head_[shead]=i;
    
31.                         }
    
32.                         if (z[i]-r<=0)
    
33.                         {
    
34.                                 sunder++;
    
35.                                 under_[sunder]=i;
    
36.                         }
    
37.                         for (j=1;j<=i;j++)
    
38.                         {
    
39.                                 if (sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]))<=2*r)
    
40.                                         if (getpar(i)!=getpar(j))
    
41.                                                 par[getpar(i)]=getpar(j);
    
42.                         }
    
43.                 }       
    
44.                 bool bb=false;
    
45.                 for (i=1;i<=shead && !bb;i++)
    
46.                         for (j=1;j<=sunder && !bb;j++)
    
47.                                 if (getpar(head_[i])==getpar(under_[j]))
    
48.                                     bb=true;
    
49.                 if (bb) cout<<"Yes"<<endl;
    
50.                 else cout<<"No"<<endl;                       
    
51.         }
    
52.         return 0;
    
53. }

复制代码

张笑宇

C:\Users\31272\Desktop