题目描述

在调度机械臂末端移动时，规划器会提供多条折线轨迹。每条轨迹由若干控制点连接而成。请在工作空间、障碍物、安全距离和总长度限制下，选出最优可执行轨迹。

有效安全半径为 R = r_tool + d_safe。轨迹的每个控制点都要在工作空间内并远离障碍物；每一段线段也要与所有矩形障碍保持至少 R 的距离。轨迹总长度不能超过 max_len。

在所有合法轨迹中，依次按总长度更短、最小安全余量更大、线段数量更少、编号更小选择。

输入格式

第一行输入工作空间矩形 xmin ymin xmax ymax。

第二行输入 r_tool d_safe max_len。

第三行输入矩形障碍数量 B。

接下来 B 行，每行输入一个矩形 x1 y1 x2 y2。

下一行输入候选轨迹数量 K。

接下来每条轨迹一行，格式为：

id P x1 y1 x2 y2 ... xP yP

其中 P 为控制点数量。

输出格式

若存在合法轨迹，输出：

id length margin_min

其中 length 为轨迹总长度，margin_min 为整条轨迹的最小安全余量，均保留 6 位小数。

若没有合法轨迹，输出 NO_TRAJECTORY。

判定规则

使用标准输出比较。安全余量允许等于 0；长度等于 max_len 时合法。工作空间边界也要扣除有效半径后判断。

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 路径长度等于 max_len 时合法，安全余量允许等于 0；不要把这些边界误判为失败。
• 工作空间边界需要扣除有效半径后判断，隐藏数据会包含刚好贴住可行边界的轨迹。
• 无合法轨迹输出 NO_TRAJECTORY；轨迹并列时优先更短、余量更大、段数更少、编号更小。

样例

输入样例 1

-1 -1 10 10
0.2 0.1 20
1
3 3 4 4
2
1 2 0 0 2 0
2 3 0 0 0 5 5 5

输出样例 1

1 2.000000 0.700000

输入样例 2

0 0 5 5
0.5 0 10
1
2 2 3 3
1
1 2 0 0 5 5

输出样例 2

NO_TRAJECTORY