@[小鼬子](/space/show?uid=77848) 然而蒟蒻我用的深搜(逃
by koosi @ 2018-08-15 18:06:21
这是我的：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f[1005],x[1005],y[1005],z[1005],a1[1005],a2[1005];
ll read(){
ll y=0;int z=1;
char x=getchar();
while (x<'0'||x>'9'){
if (x=='-') z=-1;
x=getchar();
}
while (x>='0'&&x<='9'){
y=(y<<1)+(y<<3)+x-'0';
x=getchar();
}
return y*z;
}
int find(int x){if (f[x]==x) return x; return (f[x]=find(f[x]));}
double calc(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));}
int main(){
int T=read();
while (T--){
int n=read(),m=read(),r=read(),top=0,bottom=0;
bool flag;
for (int i=1;i<=n;i++) f[i]=i;
for (int i=1;i<=n;i++){
x[i]=read();y[i]=read();z[i]=read();
if (z[i]+r>=m) a1[++top]=i;
if (z[i]-r<=0) a2[++bottom]=i;
for (int j=1;j<i;j++)
if (calc(x[i],y[i],z[i],x[j],y[j],z[j])<=(r<<1)){
int u=find(i),v=find(j);
if (u==v) continue;
f[v]=u;
}
}
flag=0;
for (int i=1;i<=top;i++){
for (int j=1;j<=bottom;j++)
if (find(a1[i])==find(a2[j])){
flag=1;
break;
}
if (flag) break;
}
if (flag) printf("Yes\n");else printf("No\n");
}
return 0;
}
```
by azure_heir @ 2018-08-15 18:11:42
@[小鼬子](/space/show?uid=77848)
by azure_heir @ 2018-08-15 18:12:24
不一定非要往越高的合并吧，忘两个两个面中的一个合并吧，以下是我的
```cpp
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
const int Maxn = 100000 + 5;
struct point{
long long X;
long long Y;
long long Z;
}Point[Maxn];
int T;
long long N,H,R;
int Set[Maxn];
bool Comp(point X,point Y){
return X.Z < Y.Z;
}
int GetFather(int X){
return Set[X] != X ? Set[X] = GetFather(Set[X]) : X;
}
void Union(int X,int Y){
int XFather = GetFather(X);
int YFather = GetFather(Y);
if(std::abs(Point[XFather].Z) <= std::abs(Point[YFather].Z))
Set[YFather] = XFather;
else Set[XFather] = YFather;
}
void Read(){
long long X,Y,Z,D;
scanf("%d",&T);
while(T --){
scanf("%lld%lld%lld",&N,&H,&R);
for(int i = 1;i <= N;++ i)
scanf("%lld%lld%lld",&Point[i].X,&Point[i].Y,&Point[i].Z);
for(int i = 1; i <= N; i++) Set[i] = i;
for(int i = 1;i <= N;++ i){
for(int j = i + 1;j <= N;++ j){
X = Point[i].X - Point[j].X;
Y = Point[i].Y - Point[j].Y;
Z = Point[i].Z - Point[j].Z;
D = X * X + Y * Y + Z * Z;
if(D <= 4 * R * R)
Union(i,j);
}
}
int P = 0;
for(int i = N;i >= 1;-- i){
if(Point[i].Z + R >= H && std::abs(Point[GetFather(i)].Z) <= R){
P = 1;
printf("Yes\n");
break;
}
}
if(!P) printf("No\n");
}
}
int main(){
Read();
return 0;
}
```
by 呼啸山庄 @ 2018-08-15 18:22:23
> 按秩合并没有必要好吗
by arfa @ 2018-08-15 18:41:57
_额，我用的深搜诶 _
by t14Zack @ 2018-08-15 19:04:17