开始看到题以为是计算几何,后面发现不是,然后秒掉了。
可能写SPFA写多了,别人都是并查集做的,我用的是SPFA。
不过无所谓,我们把题目中的下底面和上表面看成两个点,那么就是求这两个点的连通性,如果连通,出Yes,否则出No。
转换成图论,如果两个洞的半径乘2大于等于两洞球心之间的距离,那么这两个洞就直接相通,连边,总共平方复杂度建图。
然后跑SPFA,如果终点的dis不为inf,就可到达。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=+,inf=0x3f3f3f3f;
int T,n,h,p[MAXN],d[MAXN],to[MAXN*MAXN*],nex[MAXN*MAXN*],beg[MAXN],w[MAXN*MAXN*],e,s,t;
ll r;
struct node{
int x,y,z;
};
node hole[MAXN];
inline void read(int &x)
{
int data=,w=;
char ch=;
while(ch!='-'&&(ch<''||ch>''))ch=getchar();
if(ch=='-')w=-,ch=getchar();
while(ch>=''&&ch<='')data=(data<<)+(data<<)+(ch^''),ch=getchar();
x=data*w;
}
inline bool connect(int i,int j)
{
if(4ll*r*r-(ll)(hole[i].x-hole[j].x)*(ll)(hole[i].x-hole[j].x)>=(ll)(hole[i].y-hole[j].y)*(ll)(hole[i].y-hole[j].y)+(ll)(hole[i].z-hole[j].z)*(ll)(hole[i].z-hole[j].z))return true;
else return false;
}
inline void insert(int x,int y,int z)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
w[e]=z;
}
inline void Build()
{
for(register int i=;i<=n;++i)
for(register int j=i+;j<=n;++j)
if(connect(i,j))insert(i,j,),insert(j,i,);
for(register int i=;i<=n;++i)
if(hole[i].z-r<=)insert(s,i,);
for(register int i=;i<=n;++i)
if(hole[i].z+r>=h)insert(i,t,);
}
inline void SPFA()
{
for(register int i=;i<=t;++i)d[i]=inf;
queue<int> q;
q.push(s);
p[s]=;
d[s]=;
while(!q.empty())
{
int x=q.front();
q.pop();
p[x]=;
for(register int i=beg[x];i;i=nex[i])
if(d[to[i]]>d[x]+w[i])
{
d[to[i]]=d[x]+w[i];
if(!p[to[i]])
{
p[to[i]]=;
q.push(to[i]);
}
}
}
}
inline void init()
{
e=;
memset(beg,,sizeof(beg));
memset(p,,sizeof(p));
}
int main()
{
freopen("cheese.in","r",stdin);
freopen("cheese.out","w",stdout);
read(T);
while(T--)
{
init();
read(n);read(h);scanf("%lld",&r);
s=n+,t=n+;
for(register int i=;i<=n;++i)read(hole[i].x),read(hole[i].y),read(hole[i].z);
Build();
SPFA();
if(d[t]<inf)printf("Yes\n");
else printf("No\n");
}
return ;
}
NOIP2017 奶酪