P13317 [GCJ 2012 #1A] Cruise Control

巡航控制是一种让汽车以恒定速度行驶的系统，驾驶员只需控制方向盘。当然，司机可以随时关闭巡航控制以避免碰撞。 在本题中，我们考虑一条单向双车道公路，路上有 $N$ 辆车正在以巡航控制模式行驶。每辆车长 $5$ 米，并以某个恒定速度行驶。只要不会与其他车辆发生碰撞（“接触”不算碰撞），车辆可以随时变道。假设变道是瞬时完成的，只需将车辆切换到另一车道即可。我们关心的是，是否所有司机都可以一直保持恒定速度（可以变道），而永远无需关闭巡航控制来避免碰撞，或者说，是否最终有人必须减速或加速以避免碰撞。请注意，虽然变道是瞬时的，但两辆并排行驶的车辆不能同时通过变道交换位置。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据的第一行为整数 $N$，表示车辆数。接下来 $N$ 行，每行描述一辆车，包含一个字符 $C_i$（表示该车初始在左车道还是右车道），两个整数分别表示该车的速度 $S_i$（单位：米/秒）和初始位置 $P_i$（单位：米），即该车车尾距离公路某条参考线的距离。所有车辆都在远离该参考线的方向行驶，且没有车辆在参考线后方。

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为 "Possible"（仅为说明加引号，输出时不要带引号），如果所有车辆都能一直以给定速度行驶（可以变道）而无需改变速度；否则，$y$ 为最大能保持恒定速度行驶的秒数（即在某人必须改变速度以避免碰撞之前的最长时间）。答案的绝对或相对误差在 $10^{-5}$ 以内均视为正确。

**样例说明** 在第一个样例中，较快的车辆可以变道到右侧，轻松超越较慢的车辆。在第二个样例中，两辆以 $100$ m/s 行驶的车会在 $10$ 秒后追上以 $50$ m/s 行驶的车，届时两条车道都被堵住了，某辆车必须改变速度。 **限制条件** - $1 \leq T \leq 30$ - $1 \leq S_i \leq 1000$ - $0 \leq P_i \leq 10000$ - 每个 $C_i$ 字符为 $L$（左车道）或 $R$（右车道） - 初始时各车位置不会发生碰撞，即若两辆车 $i$ 和 $j$ 在同一车道（$C_i = C_j$），则 $|P_i - P_j| \geq 5$ **测试集 1（17 分，结果可见）** - $1 \leq N \leq 6$ **测试集 2（30 分，结果隐藏）** - $1 \leq N \leq 50$ 翻译由 ChatGPT-4.1 完成。