不要开根号啊, 直接拿平方和平方比, 就没有精度问题了
by ToBiChi @ 2018-06-22 14:41:51
@[tiger_tanya](/space/show?uid=47827)
by ToBiChi @ 2018-06-22 14:42:18
您的开$long \ \ long$好像没开对$\mathcal{ORZ}$
您应该完全平方式展开$dist$,用$sqrt$会导致精度误差$qwq$【话说您要是向您的代码里这样用$long$ $long$相当于没用
by 皎月半洒花 @ 2018-06-22 14:43:55
sqrt精度不够呀qwq
long long并无卵用
$ORZ$
by 绝顶我为峰 @ 2018-06-22 14:48:22
@[ToBiChi](/space/show?uid=69014)
是这样吗qwq
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=100000+10;
bool flag1,flag2,ok;
ll r,x[maxn],y[maxn],z[maxn];
int f[maxn],n,h,t;
int find(int x)
{
if(f[x]==x) return x;
else return f[x]=find(f[x]);
}
void unionn(ll x,ll y)
{
ll xx=find(x);
ll yy=find(y);
if(xx>yy)swap(xx,yy);
if(xx!=yy)
f[xx]=yy;
}
double dist(ll a,ll b)
{
return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])+(z[a]-z[b])*(z[a]-z[b]);
}
int main()
{
scanf("%d",&t);
for(int o=1;o<=t;o++)
{
flag1=false;
flag2=false;
ok=false;
scanf("%d%d%lld",&n,&h,&r);
for(int j=1;j<=n;j++)f[j]=j;
for(int j=1;j<=n;j++)
scanf("%lld%lld%lld",&x[j],&y[j],&z[j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j)
{
if(dist(i,j)<=(r*2)*(r*2))
unionn(i,j);
}
}
for(int i=1;i<=n;i++)
{
flag1=false;
flag2=false;
if(f[i]==i)
{
for(int j=1;j<=n;j++)
if(f[j]==i)
{
if(z[j]-r<=0) flag1=true;
if(z[j]+r>=h) flag2=true;
}
if(flag1==true&&flag2==true)
{ printf("Yes\n");ok=true;break;}
}
}
if(ok==false)
printf("No\n");
}
return 0;
}
```
好像还是不对的样子,喵喵喵
by tiger_tanya @ 2018-06-22 15:32:03
https://www.luogu.org/record/show?rid=4655666
我也是并查集,也开平方了,没问题,你参考一下(当时代码写得比较丑)
by GKxx @ 2018-06-22 15:53:42
话说您的$dist()$函数改完之后不应该是long long类型的吗QAQ
by 皎月半洒花 @ 2018-06-22 15:55:02
@[tiger_tanya](/space/show?uid=47827)
by 皎月半洒花 @ 2018-06-22 15:55:43
@[皎月半洒花](/space/show?uid=28313)
哎,好像粘错代码了。
是这个
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int maxn=100000+10;
bool flag1,flag2,ok;
ll r,x[maxn],y[maxn],z[maxn];
int f[maxn],n,h,t;
int find(int x)
{
if(f[x]==x) return x;
else return f[x]=find(f[x]);
}
void unionn(ll x,ll y)
{
ll xx=find(x);
ll yy=find(y);
if(xx>yy)swap(xx,yy);
if(xx!=yy)
f[xx]=yy;
}
ll dist(int a,int b)
{
return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])+(z[a]-z[b])*(z[a]-z[b]);
}
int main()
{
scanf("%d",&t);
for(int o=1;o<=t;o++)
{
flag1=false;
flag2=false;
ok=false;
scanf("%d%d%lld",&n,&h,&r);
for(int j=1;j<=n;j++)f[j]=j;
for(int j=1;j<=n;j++)
scanf("%lld%lld%lld",&x[j],&y[j],&z[j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j)
{
if(dist(i,j)<=4*r*r)
unionn(i,j);
}
}
for(int i=1;i<=n;i++)
{
flag1=false;
flag2=false;
if(f[i]==i)
{
for(int j=1;j<=n;j++)
if(f[j]==i)
{
if(z[j]-r<=0) flag1=true;
if(z[j]+r>=h) flag2=true;
}
if(flag1==true&&flag2==true)
{ printf("Yes\n");ok=true;break;}
}
}
if(ok==false)
printf("No\n");
}
return 0;
}
```
by tiger_tanya @ 2018-06-22 15:58:47
@[GKxx](/space/show?uid=72071) 谢谢大佬qwq
by tiger_tanya @ 2018-06-22 15:59:53