题解 P3958 【奶酪】

简单易懂：强搜 首先，两个洞相切或相交，那么便是一种相连关系，如果将洞看成点，相连的状态看成边，下底是点0，上表面是点n+1，则问题转化为给定一个无向图，求是否能从0号点到n+1号点 那么问题来了： # 如何判断两个球相交/切？ ## 显然，两个球半径之和≥球心之和那么两球相交 建图和遍历就不用讲了，我用的是懒人vector存图，各位也可以写链式前向星，主要看个人喜好。 下面是代码： --- ```cpp #define maxn 1000+50 //直接maxn岂不美滋滋 #include<cstdio> #include<algorithm> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> //头文件 #define LL long long //敲黑板划重点啦！long long不开后果自负 using namespace std; vector<int> g[maxn]; //vector大法好 int vis[maxn],x[maxn],y[maxn],z[maxn]; //从左至右，标记数组和坐标 double dis(LL x1,LL y1,LL z1,LL x2,LL y2,LL z2) //求两点直线距离 { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2)); } void dfs(int u) //遍历全图 { vis[u]=1; //打上标记 for (int i=0;i<g[u].size();++i) //找每一个u的后继 { int v=g[u][i]; if (!vis[v]) dfs(v); //如果未访问，则访问 } } int main() { int T; scanf("%d",&T); //数据组数 while (T--) //这样写简单 { LL n,h,r; scanf("%lld%lld%lld",&n,&h,&r); for (int i=1;i<=n;++i) scanf("%lld%lld%lld",&x[i],&y[i],&z[i]); for (int i=0;i<=n+1;++i) g[i].clear(); //清空图 for (int i=1;i<n;++i) //枚举每两个空洞 for (int j=i+1;j<=n;++j) if (dis(x[i],y[i],z[i],x[j],y[j],z[j])<=r*2) //判断相交 { g[i].push_back(j); g[j].push_back(i); } for (int i=1;i<=n;++i) if (z[i]<=r) g[0].push_back(i); //判断和下底的相交，用高度和半径比 for (int i=1;i<=n;++i) if (z[i]+r>=h) g[i].push_back(n+1); //判断和上表面的相交，用高度加半径和顶上的高度比 memset(vis,0,sizeof(vis)); //清空标记准备灌水 dfs(0); if (vis[n+1]) puts("Yes"); //如果n+1被搜到了，就是成功爬出 else puts("No"); //否则就是被Tom吃掉 } return 0; } ```