【NOIP2017】 奶酪
解题思路：
同样的，可以用dfs做，但是有没有发现，用并查集做会更加地，简单？
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
struct node{
long long high,low;
long long x,y,z;
};
long double dist(node p,node q)
{
return (long double)sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)+(p.z-q.z)*(p.z-q.z));
}
int f[100010];
int get(int x)
{
return f[x]=(x==f[x]? x:get(f[x]));
}
void merge(int x,int y)
{
f[get(x)]=get(y);
}
void init()
{
for(int i=1;i<=100000;i++)
f[i]=i;
}
int T;
int main()
{
cin>>T;
while(T--)
{
init();
long long n,h,r;
cin>>n>>h>>r;
node a[1005];
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y>>a[i].z;
int highest[1005]={0};
int tot1=0;
int lowest[1005]={0};
int tot2=0;
for(int i=1;i<=n;i++)
{
a[i].high=a[i].z+r;
a[i].low= a[i].z-r;
if(a[i].high>=h)
{
++tot1;
highest[tot1]=i;
}
if(a[i].low<=0)
{
++tot2;
lowest[tot2]=i;
}
for(int j=i;j<=n;j++)
{
if(dist(a[i],a[j])<=2*r)
merge(i,j);
}
}
bool flag=false;
for(int i=1;i<=tot1;i++)
{
for(int j=1;j<=tot2;j++)
{
if(get(highest[i])==get(lowest[j]))
{
flag=true;
cout<<"Yes"<<endl;
break;
}
}
if(flag) break;
}
if(flag) continue;
else
cout<<"No"<<endl;
}
return 0;
}
|
