谨以此题来纪念我爆炸的NOIp2017
这个题虽然很多人说是并查集,但是搜索也是毫无压力的,考场搜索细节写挂,爆了个不上不下的80分。今天无意看到这道题，终于AC
首先这道题要考虑一下精度问题,虽然出题人没有毒瘤的卡精度,但还是要值得注意。解决方法也很简单,去除开方运算,而是将半径平方,即\(2r\) ---> \(4r^2\),这样就OK了。不过要记得用\(\rm long\;long\),不然会爆\(\rm int\)
然后考虑如何搜索,我是将每组数据用前向星存成图,然后搜这张图。这道题有一个很特别的地方,那就是它不用回溯,因为如果一个点到不了终点,那再次搜到的话也还是到不了终点,所以我们为什么要将它再搜一遍呢?直接丢掉就好了
上代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
inline int read() //快读
{
int k=0,f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())
if(c=='-')f=-1;
for(;isdigit(c);c=getchar())
k=k*10+c-48;
return k*f;
}
struct zzz{ //存空洞的坐标
ll x,
y,
z;
}che[1001];
inline ll f(zzz x,zzz y) //计算空洞距离
{
return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)+(x.z-y.z)*(x.z-y.z);
}
struct hhh{ //存图
int f,
t,
nex;
}e[2000001]; int head[1001]; int tot;
inline void add(int x,int y) //前向星
{
e[++tot].f=x;
e[tot].t=y;
e[tot].nex=head[x];
head[x]=tot;
}
int s[1001],flag; bool en[1001],vis[1001];
//s:可以当作起点的空洞 flag:可以当作起点的空洞的个数 en:终点空洞 vis:这个点是否走过
bool ans; //判断能否到达上表面
void dfs(int str) //搜索主体
{
if(en[str]) //找到终点就不用搜了
{
ans=1; return ;
}
for(int i=head[str];i;i=e[i].nex) //向下寻找能搜的点
if(!vis[e[i].t])
{
vis[e[i].t]=1; //直接标志为搜过,不再回溯
dfs(e[i].t); //向下搜索
if(ans)
return ;
}
}
int main()
{
int t; t=read();
int n; ll h,r;
while(t--)
{
tot=0; memset(head,0,sizeof(head)); ans=0;
flag=0; memset(en,0,sizeof(en)); memset(vis,0,sizeof(vis)); //清空所有变量
n=read(),h=read(),r=read();
for(int i=1;i<=n;i++) //输入数据 + 处理成图
{
che[i].x=read(),che[i].y=read(),che[i].z=read();
if(che[i].z<=r) //如果z>=半径,那么这个空洞和下表面接触,将它加入起点
s[++flag]=i;
if(che[i].z>=h-r) //同理,如果z>=h-r,那它和上表面接触,将它加入终点
en[i]=1;
for(int j=1;j<i;j++)
if(f(che[i],che[j])<=4*r*r) //防止精度损失
{
add(i,j); add(j,i);
}
}
// 搜索 + 输出
bool jjj=0;
for(int i=1;i<=flag;i++)
{
dfs(s[i]);
if(ans)
{
printf("Yes\n");
jjj=1;
break;
}
}
if(!jjj)
printf("No\n");
}
return 0;
}- 打个广告吧