AEAI-04-003. 三维参考物体最近邻选择

题目描述

机械臂在整理桌面物体时，需要知道哪个物体离当前参考物体最近，从而判断是否需要额外避让。给出若干物体的三维坐标、一个参考物体编号 R，以及安全距离阈值 d_safe。请在除参考物体以外的物体中，选出与参考物体三维欧氏距离最小的物体，并输出它的距离和安全标记。

设某个物体相对参考物体的坐标差为 (dx, dy, dz)，距离定义为：

sqrt(dx*dx + dy*dy + dz*dz)

若多个物体到参考物体的距离相同，选择编号更小的物体。若选中物体的距离小于等于 d_safe，安全标记为 NEAR，否则为 NORMAL。

输入格式

第一行输入整数 N，表示物体数量。

接下来 N 行，每行输入：

id x y z

表示物体编号和三维坐标。所有编号互不相同。

下一行输入参考物体编号 R。

最后一行输入一个实数 d_safe。

输出格式

输出一行：

id distance status

其中 id 为最近物体编号，distance 为该物体到参考物体的距离，保留 6 位小数；status 为 NEAR 或 NORMAL。

判定规则

使用标准输出比较。浮点比较使用 1e-9 容差；距离相同时按编号升序打破并列；距离等于 d_safe 时输出 NEAR。

数据范围与提示

• 2 <= N <= 100000
• 坐标为有限实数。
• d_safe >= 0
• 输入保证参考物体编号存在。
• 建议比较平方距离，最后只对选中物体开平方输出。

样例 1

输入

4
1 0 0 0
2 3 0 0
3 0 4 0
4 1 2 2
1
3

输出

2 3.000000 NEAR

样例 2

输入

3
10 1 1 1
5 4 5 1
8 1 1 6
10
4

输出

5 5.000000 NORMAL