带禁入区的抓取可达性判断 题解

核心思路

对每个候选抓取点按题面给定优先级依次检查：

1. 检查高度 z 是否在 [zmin, zmax] 内，不满足则输出 HEIGHT。
2. 计算水平半径 rho = sqrt(x^2 + y^2)，检查是否在 [rmin, rmax] 内，不满足则输出 RADIUS。
3. 枚举所有禁入区，若点在圆形禁入区内部或边界上，输出 FORBIDDEN_CIRCLE；若点在矩形禁入区内部或边界上，输出 FORBIDDEN_RECT。
4. 若点到最近禁入区的距离 <= d_safe，输出 UNSAFE。
5. 否则输出 EXECUTABLE 和 rmax - rho。

距离计算

圆形禁入区 C cx cy r：

distance = sqrt((x - cx)^2 + (y - cy)^2) - r

若 distance <= 0，点在圆内或圆边界上，属于 FORBIDDEN_CIRCLE。

矩形禁入区 R x1 y1 x2 y2：

• 若 x1 <= x <= x2 且 y1 <= y <= y2，距离为 0，属于 FORBIDDEN_RECT。
• 否则分别计算点到矩形水平范围和竖直范围的外部距离，再用欧氏距离合成。

正确性说明

算法对每个候选点严格按照 HEIGHT > RADIUS > FORBIDDEN_CIRCLE/FORBIDDEN_RECT > UNSAFE > EXECUTABLE 的顺序判断。若某一步失败，题目要求输出首个失败原因，算法立即输出并跳过后续检查，因此输出状态与优先级一致。若点同时落入多个禁入区，算法按输入顺序返回第一个命中的禁入区类型。

通过高度和半径检查后，算法枚举所有禁入区，能够发现点是否落入任意圆形或矩形禁入区，并输出对应的禁入区类型；若未落入，再取到所有禁入区的最小距离与 d_safe 比较，因此能够正确区分禁入、过近和可执行。可执行时输出的 margin 正是题面定义的 rmax - sqrt(x^2 + y^2)。

复杂度

设候选点数量为 N，禁入区数量为 K。

时间复杂度：O(NK)。

空间复杂度：O(K)。

常见错误

• 把禁入区边界当成可执行点，或没有区分圆形和矩形禁入区类型。
• 把距离等于 d_safe 的点当成安全，导致应输出 UNSAFE 的点被误判。
• 在同时高度越界和落入禁区时输出了后面的失败原因，忽略了固定优先级。
• 忘记对 EXECUTABLE 的 margin 保留 6 位小数。