AEAI-04-004. 带禁入区的抓取可达性判断

题目描述

机械臂执行抓取前，需要对一批候选抓取点做可达性与安全性检查。每个候选点给出编号 id 和三维坐标 (x, y, z)。

机械臂的工作空间由两部分组成：

• 高度范围 [zmin, zmax]；
• 水平半径范围 [rmin, rmax]，其中水平半径为 sqrt(x^2 + y^2)。

桌面上还存在若干平面禁入区。禁入区只使用点的 (x, y) 坐标判断，可以是圆形或轴对齐矩形。候选点必须不落入禁入区，并且到所有禁入区的最短平面距离都要严格大于安全距离 d_safe，才可以执行。

对每个候选点，按固定顺序检查并输出第一个命中的状态：

1. 若 z 不在 [zmin, zmax] 内，输出 HEIGHT。
2. 否则，若 sqrt(x^2 + y^2) 不在 [rmin, rmax] 内，输出 RADIUS。
3. 否则，若 (x, y) 落入任意圆形禁入区内部或边界，输出 FORBIDDEN_CIRCLE；若落入任意矩形禁入区内部或边界，输出 FORBIDDEN_RECT。若同时落入多个禁入区，按输入中最先命中的禁入区类型输出。
4. 否则，若 (x, y) 到任意禁入区的最短距离 <= d_safe，输出 UNSAFE。
5. 否则，该点可执行，输出 EXECUTABLE 以及到最大半径边界的剩余量 rmax - sqrt(x^2 + y^2)。

输入格式

第一行输入 rmin rmax zmin zmax。

第二行输入禁入区数量 K。

接下来 K 行描述禁入区：

• C cx cy r 表示圆形禁入区，圆心为 (cx, cy)，半径为 r；
• R x1 y1 x2 y2 表示矩形禁入区，左下角为 (x1, y1)，右上角为 (x2, y2)。

接下来一行输入安全距离 d_safe。

下一行输入候选抓取点数量 N。

接下来 N 行，每行输入 id x y z。

输出格式

对每个候选抓取点按输入顺序输出一行：

• 高度越界：id HEIGHT
• 半径越界：id RADIUS
• 落入圆形禁入区：id FORBIDDEN_CIRCLE
• 落入矩形禁入区：id FORBIDDEN_RECT
• 到禁入区距离不超过安全距离：id UNSAFE
• 可执行：id EXECUTABLE margin

其中 margin 保留 6 位小数。

判定规则

使用标准输出比较。

圆形禁入区的距离计算为 sqrt((x - cx)^2 + (y - cy)^2) - r。若该值小于等于 0，表示点在圆形禁入区内部或边界上，状态为 FORBIDDEN_CIRCLE。

矩形禁入区内部及边界到矩形的距离为 0，状态为 FORBIDDEN_RECT。矩形外部点到矩形的距离为该点到矩形边界的最短欧氏距离。

若候选点同时满足多个失败条件，只输出优先级最高的一个。优先级固定为：

HEIGHT > RADIUS > FORBIDDEN_CIRCLE/FORBIDDEN_RECT > UNSAFE > EXECUTABLE

边界规则：

• 高度和半径刚好等于上下界时，仍视为通过对应工作空间检查。
• 禁入区边界视为落入禁入区，按禁入区类型输出 FORBIDDEN_CIRCLE 或 FORBIDDEN_RECT。
• 到禁入区距离刚好等于 d_safe 时，输出 UNSAFE。

数据范围与测试提示

• 正式测试会覆盖高度边界、半径边界、圆形禁入区边界、矩形禁入区边界和安全距离等号边界。
• 圆形和矩形禁入区可能混合出现。
• 输出只包含题目要求的字段，不要输出调试信息。
• 浮点结果按题面要求保留 6 位小数。

样例

输入样例 1

1 10 0 5
2
C 3 0 1
R 6 1 8 3
0.5
5
1 5 0 2
2 5 0 6
3 0.5 0 2
4 3 0 2
5 4.5 0 2

输出样例 1

1 EXECUTABLE 5.000000
2 HEIGHT
3 RADIUS
4 FORBIDDEN_CIRCLE
5 UNSAFE

输入样例 2

0 10 0 5
1
R 2 2 4 4
1
3
1 3 3 1
2 1.2 3 1
3 8 0 1

输出样例 2

1 FORBIDDEN_RECT
2 UNSAFE
3 EXECUTABLE 2.000000