Problem D: 2025AHCPC_D机器人学

上一题 正确率: $INF\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $11$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

 机器人学是人工智能的重要组成部分,在机器人技术课程中,小明学习了二维坐标下的机器人运动控制相关知识.在多智能体协作中,每个机器人都能从周围的视觉信息中获取一个图元的方位信息,通过相互传递这些信息,机器人都可以重建出整个周围环境的绝对坐标,进而进行智能决策.

         小明为了考考你,从旁边的机器人实验室中获得了灵感,在同期进行的机器人赛道 RoboCup2D 机器人足球比赛中,位置信息是通过两种方式表示的,分别是球员坐标和球场坐标系.球场坐标系是一个常见的直角坐标系,用于通过上帝视角描述各要素的位置;而球员坐标系是一个以自身为原点的极坐标系,坐标系夹角以球员面向方向为零角,用 (r,theta) 表示一个要素的位置,其中 r 为坐标原点到要素的距离, theta 为以球员面向方向为零角,逆时针旋转的角度.

         在比赛中,机器人球员通过自身视觉系统可以很简单地获取到球相对于球员坐标系的角度,但由于机器人没有装备设备激光雷达,便没办法得知球相对于自身的距离.但是我们可以通过多个球员的协作来确定位置,正常情况下,两个球员所目击的球的角度,结合球员自身的方位,便可以确定球的位置.

         但是为了增加比赛难度,亦是为了模拟真实环境,组委会向比赛场地中添加了噪声,即球员获取的球的方位信息可能是延迟的或是出错的.为了确保球的位置识别正确,小明想到了这种方法,当且仅当任意三个球员视线 (从球员面朝方向引出的射线) 所围成的三角形区域面积小于球的最大横截面积的 1.5 倍,即可认为这三个球员可以确定准确的球的位置.

         小明需要你的帮助,针对每种情况下球员识别出的球的位置,判断这种情况下机器人们能否确定球的准确位置.


Input

    一个整数 T,代表测试数据组数.

         对于每组测试数据,

         一行一个整数 n 以及一个浮点数 S 代表球的最大横截面积,每行 4 个浮点数 x,y,vec,pos,代表球员所在球场坐标系绝对坐标位置和球员当前面朝方向,以及球员坐标系下球员目击到的球的方向,方向数据均用角度值表示.

Output

         输出 T 行,判断当前信息能否确定球的位置,若可以,输出 YES,否则输出 NO.

Sample Input复制

3
3 0.5
0 0 0 45
1 0 0 90
2  2 180 0
3 0.5
0 0 0 45
1 0 0 90
2 3 180 0
3 0.01
0 0 0 45
1 0 0 90
2 3 180 0

Sample Output复制

YES
NO
NO

提示

数据规模与约定

         对于 100% 的数据, 1≤N≤20,1≤T≤100,−100≤x,y,r≤100,−180<vec,pos≤180.

样例解释

         对于该问题,球员方位及围成面积如图所示.可以很容易地求出面积.

         其中,箭头方向代表球员面朝方向,射线代表球员目击到的球的方向.


         针对其中一种答案为 NO 的情况,可能是机器人的视线没有形成有效的三角形.