P13374 [GCJ 2011 #2] Airport Walkways

你现在在机场，站在 $0$ 点。通往登机口的走廊长度为 $X$ 米，你的飞机即将起飞。走廊上有若干条自动步道，每条步道的速度为 $w_i$。当你在步道上行走或奔跑时，你的速度为（你的速度 $+$ $w_i$）。步道不会移动它们的位置，只是让你移动得更快。步道之间不会重叠：在走廊的任意一点，至多只有一条步道，但一条步道可以在另一条步道结束的地方开始。 你的正常步行速度为 $S$。你担心可能赶不上飞机，因此你可以选择奔跑一段时间——你最多可以以速度 $R$ 奔跑 $t$ 秒。你不需要连续奔跑 $t$ 秒：你可以将这 $t$ 秒分成任意多个时间段，甚至可以不用完全部时间。 请问，在你合理安排步行和奔跑的情况下，最短需要多少时间才能到达登机口 $X$ 点？

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为五个整数：$X$（走廊长度，单位为米）、$S$（步行速度，单位为米/秒）、$R$（奔跑速度，单位为米/秒）、$t$（最大奔跑时间，单位为秒）、$N$（步道数量）。 接下来的 $N$ 行，每行包含三个整数：$B_i$、$E_i$ 和 $w_i$，分别表示第 $i$ 条步道的起点、终点（距离起点的米数）以及步道的速度（单位为米/秒）。

对于每组测试数据，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试编号（从 $1$ 开始），$y$ 是你到达 $X$ 点所需的最短时间（单位为秒）。当且仅当你的答案的相对或绝对误差不超过 $10^{-6}$ 时，才会被判为正确。

**样例解释** 在第一个样例中，最优的做法是立即开始奔跑，并奔跑 1 秒。 **数据范围** - $1 \leq T \leq 40$。 - $1 \leq S < R \leq 100$。 - $1 \leq w_i \leq 100$。 - $0 \leq B_i < E_i \leq X$。 - $E_i \leq B_{i+1}$。 **小数据集（8 分，测试集 1 - 可见）** - $1 \leq t \leq 100$。 - $1 \leq X \leq 100$。 - $1 \leq N \leq 20$。 - 时间限制：3 秒。 **大数据集（10 分，测试集 2 - 隐藏）** - $1 \leq t \leq 10^6$。 - $1 \leq X \leq 10^6$。 - $1 \leq N \leq 1000$。 - 时间限制：6 秒。 由 ChatGPT 4.1 翻译