并查集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