传送门

思路:

  模拟题。用并查集求出所有 “连通块” ,判断是否有 “连通块” 的最顶上和最下方都不小于奶酪的范围。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdlib>
#include<stack>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
#define lck_max(a,b) ((a)>(b)?(a):(b))
#define lck_min(a,b) ((a)<(b)?(a):(b))
#define INF 1e9+7
typedef long long LL;
const int maxn=1e3+;
LL T,n,h,r,up_cnt,down_cnt,fa[maxn];
bool flag;
struct hh
{
LL x,y,z,up,down;
}t[maxn*maxn];
inline LL read()
{
LL kr=,xs=;
char ls;
ls=getchar();
while(!isdigit(ls))
{
if(!(ls^))
kr=-;
ls=getchar();
}
while(isdigit(ls))
{
xs=(xs<<)+(xs<<)+(ls^);
ls=getchar();
}
return xs*kr;
}
inline LL find(LL u)
{
return u==fa[u]?u:fa[u]=find(fa[u]);
}
inline double dis(LL u,LL v)
{
return sqrt((t[u].x-t[v].x)*(t[u].x-t[v].x)+(t[u].y-t[v].y)*(t[u].y-t[v].y)+(t[u].z-t[v].z)*(t[u].z-t[v].z));
}
int main()
{
freopen("cheese.in","r",stdin);
freopen("cheese.out","w",stdout);
T=read();
while(T--)
{
flag=false,up_cnt=,down_cnt=;
n=read();h=read();r=read();
for(LL i=;i<=n;i++) fa[i]=i;
for(LL i=;i<=n;i++)
{
t[i].x=read();t[i].y=read();t[i].z=read();
if(t[i].z+r>=h) t[++up_cnt].up=i;
if(t[i].z-r<=) t[++down_cnt].down=i;
for(LL j=;j<i;j++)
{
if(dis(i,j)>*r) continue;
LL r1=find(fa[i]),r2=find(fa[j]);
if(r1!=r2) fa[r1]=r2;
}
}
for(LL i=;i<=up_cnt;i++)
for(LL j=;j<=down_cnt;j++)
{
LL r1=find(t[i].up),r2=find(t[j].down);
if(r1==r2) {flag=true;break;}
}
if(!flag) printf("No\n");
else printf("Yes\n");
}
fclose(stdin);
fclose(stdout);
return ;
}

最新文章

  1. Choosing Columns and Expressions to Index
  2. .net MVC APi调用
  3. 使用SQL Server 2014内存数据库时需要注意的地方
  4. jquery ui 插件-------------------------&gt;sortable
  5. yii2学习的论坛
  6. POJ 2632 Crashing Robots (坑爹的模拟题)
  7. RealThinClient学习(一)
  8. PL/SQL联系oracle成功可以sql解决的办法是检查表的名称无法显示
  9. PHP童鞋改JAVA代码怎么处理
  10. Lustre文件系统测试——obdfilter-survey测试
  11. HighCharts之2D面积图
  12. 带你深入理解STL之Deque容器
  13. mac 利用svn下载远程代码出现Agreeing to the Xcode/iOS license requires admin privileges, please re-run as root via sudo.
  14. 深度学习课程笔记(九)VAE 相关推导和应用
  15. Lintcode455-StudentID-Easy
  16. selenium 操作文本框(textarea输入)
  17. UI5-文档-4.24-Filtering
  18. 处理DateTime.Now不经过ToString()转换的格式(带有AM、PM)问题
  19. python模块之imghdr检测图片类型
  20. VideoJS 与 Framework7 中 fastclick 冲突问题

热门文章

  1. Spring AOP capabilities and goals
  2. springMVC--annotation
  3. Leetcode: The Maze(Unsolved locked problem)
  4. 微信小程序案例大全
  5. docker容器实战-----初级&lt;2&gt;
  6. ASP.NET gridview导出excel,防止繁体产生有乱码的方式
  7. 关于Xamarin、Qml、数据绑定、MVC、MVVM 相关的散讲
  8. Xamarin.Forms + Prism,整理页面导航跳转流程
  9. layer —— 一个简单的jQuery弹出层插件
  10. vue获得当前页面URL动态拼接URL复制邀请链接方法