• 应用
• 登录
• 注册

# 并查集50

@北洋张学良 2018-11-09 09:38 回复

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
long long x[1000000];long long y[1000000];long long z[1000000];
int f1[1000000],f2[1000000],f[1000000];
long long juli(long long x,long long y,long long z,long long p,long long q,long long o){
return (x-p)*(x-p)+(y-q)*(y-q)+(z-o)*(z-o);
}
int laoda(int v){
if(v==f[v])return v;
else {
f[v]=laoda(f[v]);
return f[v];
}
}
void hebing(int a,int b){
int t1=laoda(a);
int t2=laoda(b);
if(t1!=t2){
f[t2]=t1;
}
}
int main(){
freopen("cheese.in","r",stdin);
freopen("cheese.out","w",stdout);
int t;
int i,j,k;
scanf("%d",&t);
for(k=1;k<=t;k++){
int n;
long long r,h;int flag=0;
int num1=0,num2=0;
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(z,0,sizeof(z));
memset(f1,0,sizeof(f1));
memset(f2,0,sizeof(f2));
memset(f,0,sizeof(f));
scanf("%d%lld%lld",&n,&h,&r);
for(j=1;j<=n;j++)
f[j]=j;
for(j=1;j<=n;j++){
scanf("%lld%lld%lld",&x[j],&y[j],&z[j]);
if(z[j]+r>=h)
{
num1++;
f1[num1]=j;
}
if(z[j]-r<=0){
num2++;
f2[num2]=j;
}
for(i=1;i<=j;i++)
if(juli(x[i],y[i],z[i],x[j],y[j],z[j])<=4*r*r)
hebing(i,j);
}
for(i=1;i<=num1;i++){
for(j=1;j<=num2;j++){
if(laoda(f1[i])==laoda(f2[j]))
flag=1;
break;
}
if(flag==1)break;
}
if(flag==1)printf("Yes\n");
else printf("No\n");
}
return 0;
}
@Ruirui_170219 2018-11-09 10:29 回复

@北洋张学良 您好，对于下面这组数据，你的输出是 No，正确的输出是 Yes

1
31 181 101
632 844 24
-884 -236 670
-315 -480 12
94 -934 26
328 775 686
758 -290 686
-723 -622 828
-712 -388 717
534 -272 706
-98 -660 540
105 -833 488
344 72 90
432 -423 412
615 768 875
585 540 908
278 860 478
-370 -746 830
344 375 134
-610 84 830
-760 978 688
-870 -225 648
-606 -566 252
-568 -127 798
264 -347 846
-662 -1000 950
-50 197 790
-552 -432 760
552 128 388
317 456 312
-651 -640 871
-981 -608 88
@北洋张学良 2018-11-09 10:33 回复
    if(flag==1)break;
}
这里删了`