社区讨论
我是怎么AC的
P3958[NOIP 2017 提高组] 奶酪参与者 4已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xypxu
- 此快照首次捕获于
- 2025/11/20 12:38 4 个月前
- 此快照最后确认于
- 2025/11/20 12:38 4 个月前
RT,思路类似第一篇题解
但貌似我这个连样例都过不了
可是AC了?
#include<bits/stdc++.h>
#define MEM memset
#define DURU scanf
const int MAXS=100000+5;
using namespace std;
long long X[MAXS],Y[MAXS],Z[MAXS];
int F1[MAXS],F2[MAXS],DAD[1000+5];
long long DIS(long long X1,long long X2,long long Y1,long long Y2,long long Z1,long long Z2){
return (X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)+(Z1-Z2)*(Z1-Z2);
}
int FIND(int X){
if(DAD[X]!=X)
return DAD[X]=FIND(DAD[X]);
else return X;
}
int main( ){
long long R; int H,M,T;
DURU("%d",&T);
while(T--){
DURU("%d%d%ld",&M,&H,&R);
int SUM1=0,SUM2=0,FLAG=0;
for(register int I=1;I<=M;I++)
DAD[I]=I;
for(register int I=1;I<=M;I++){
DURU("%ld%ld%ld",&X[I],&Y[I],&Z[I]);
if(Z[I]+R>=H)F1[++SUM1]=I;
if(Z[I]-R<=0)F2[++SUM2]=I;
for(register int J=1;J<=I;J++){
if(DIS(X[I],X[J],Y[I],Y[J],Z[I],Z[J])<=4*R*R){
int U=FIND(I),V=FIND(J);
if(U!=V)DAD[U]=V;
}
}
}
for(register int I=1;I<=SUM1;I++){
for(register int J=1;J<=SUM2;J++){
if(FIND(F1[I])==FIND(F2[J])){
FLAG=1; break;
}
}
if(FLAG==1)break;
}
if(FLAG==1)
cout<<"Yes"<<endl;
if(FLAG==0)
cout<<"No"<<endl;
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...