(中间用了小小的 goto QAQ)
by mureZ @ 2018-09-19 00:08:22
为什么大家都喜欢 $sqrt$ 呢,明明不需要开出来啊
by WorldBest丶牛顿 @ 2018-09-19 00:23:06
@[mureZ](/space/show?uid=25169)
```cpp
fa[x]=fa[find(x)]
```
没问题吗,感觉应该是
```cpp
fa[x]=find(fa[x])
```
by WorldBest丶牛顿 @ 2018-09-19 00:26:42
你的本机 AC 是怎么回事?
by memset0 @ 2018-09-19 07:17:06
...确实是find写错了。。。
但是改好后678WA了。。。
```cpp
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n,h,r,QAQ,QWQ;
struct P{
long long x,y,z;
};
long long dist(P p1,P p2){
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z);
}
bool access(P p1,P p2){
if (4*r*r>=dist(p1,p2)) return 1;
return 0;
}
bool cmp(P p1,P p2){
return p1.z<p2.z;
}
P a[1005];
//Point struct & judgement & init
int fa[1005]={0};
int find (int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void combine (int a,int b){
fa[find(a)]=find(b);
}
//并查集
int up[1001];
int bottom[1001];
int main(){
cin>>QWQ;
for (int QAQ=1;QAQ<=QWQ;QAQ++){//QAQ
cin>>n>>h>>r;
for (int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+n+1,cmp);
int upnum=1;
for (int i=1;i<=n;i++){
if (h-a[i].z<=r)up[upnum++]=i;
}
upnum--;
int bottomnum=1;
for (int i=1;i<=n;i++){
if (a[i].z<=r)bottom[bottomnum++]=i;
}
bottomnum--;
if (upnum==0||bottomnum==0) goto NO;
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=2;i<=n;i++){
if (fa[i]==i){
for (int j=1;j<=n;j++){
if (access(a[i],a[j])&&i!=j){
combine(max(i,j),min(i,j));
break;
}
}
}
}
for (int i=n;i>=n-upnum;i--){
for (int j=1;j<=bottomnum;j++){
if (find(i)==find(j)){
cout<<"Yes"<<endl;
goto YES;
}
}
}
NO:
QAQ+=0;
cout<<"No"<<endl;
YES:
QAQ+=0;
}
return 0;
}
```
by mureZ @ 2018-09-19 10:07:42
```
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
int n,h,r,QAQ,QWQ;
struct P{
long long x,y,z;
};
double dist(P p1,P p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}
bool access(P p1,P p2){
if (2*r>=dist(p1,p2)) return 1;
return 0;
}
bool cmp(P p1,P p2){
return p1.z<p2.z;
}
P a[1005];
//Point struct & judgement & init
int fa[1005]={0};
int find (int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void combine (int a,int b){
fa[find(a)]=find(b);
}
//并查集
int up[1001];
int bottom[1001];
int main(){
cin>>QWQ;
for (int QAQ=1;QAQ<=QWQ;QAQ++){//QAQ
cin>>n>>h>>r;
for (int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+n+1,cmp);
int upnum=1;
for (int i=1;i<=n;i++){
if (h-a[i].z<=r)up[upnum++]=i;
}
upnum--;
int bottomnum=1;
for (int i=1;i<=n;i++){
if (a[i].z<=r)bottom[bottomnum++]=i;
}
bottomnum--;
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=2;i<=n;i++){
if (fa[i]==i){
for (int j=1;j<=n;j++){
if (access(a[i],a[j])&&i!=j){
combine(max(i,j),min(i,j));
break;
}
}
}
}
for (int i=n;i>n-upnum;i--){
for (int j=1;j<=bottomnum;j++){
if (find(i)==find(j)){
cout<<"Yes"<<endl;
goto YES;
}
}
}
cout<<"No"<<endl;
YES:
QAQ+=0;
}
return 0;
}
```
by mureZ @ 2018-09-19 10:09:20
谢谢大家,已经AC
```cpp
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
int n,h,r,QAQ,QWQ;
struct P{
long long x,y,z;
};
double dist(P p1,P p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
}
bool access(P p1,P p2){
if (2*r>=dist(p1,p2)) return 1;
return 0;
}
bool cmp(P p1,P p2){
return p1.z<p2.z;
}
P a[1005];
//Point struct & judgement & init
int fa[1005]={0};
int find (int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
void combine (int a,int b){
fa[find(a)]=find(b);
}
//并查集
int up[1001];
int bottom[1001];
int main(){
cin>>QWQ;
for (int QAQ=1;QAQ<=QWQ;QAQ++){//QAQ
cin>>n>>h>>r;
int upnum=1,bottomnum=1;
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y>>a[i].z;
if (h-a[i].z<=r)up[upnum++]=i;
if (a[i].z<=r)bottom[bottomnum++]=i;
for (int j=1;j<i;j++){
if (access(a[i],a[j])){
combine(max(i,j),min(i,j));
}
}
}
upnum--;
bottomnum--;
for (int i=1;i<=upnum;i++){
for (int j=1;j<=bottomnum;j++){
if (find(up[i])==find(bottom[j])){
cout<<"Yes"<<endl;
goto YES;
}
}
}
cout<<"No"<<endl;
YES:
QAQ+=0;
}
return 0;
}
```
by mureZ @ 2018-09-19 10:28:06
issue closed
by mureZ @ 2018-09-19 17:31:33
是不是Yes No 打错了。。。
by Sniper_lyb @ 2018-09-26 21:56:37
@[Rookiee](/space/show?uid=26008) 好吧没看到已经解决了。。。
by Sniper_lyb @ 2018-09-26 21:57:10