Description

从摩洛哥到西班牙穿越直布罗陀海峡的渡轮必须小心导航，以避免海峡内繁忙的船只交通。编写一个程序帮助渡轮船长找到海峡交通中最大的空隙，以便安全穿越。

你的程序将使用如下简单模型。海峡有几条东西方向的平行航道。船只以相同的恒定速度向东或向西航行。同一航道上的所有船只都朝同一方向航行。卫星数据提供了每条航道上船只的位置。船只可能有不同的长度。船只在渡轮穿越时不会改变航道，也不会改变速度。

渡轮等待适当的时间，当船只交通中有足够的空隙时，它就穿越海峡，沿南北方向以恒定速度航行。从渡轮进入航道的那一刻起，直到它离开航道的那一刻，该航道中的任何船只都不得碰触渡轮的穿越线。渡轮非常小，你可以忽略它的大小。下图展示了样例输入 1 的航道和船只。你的任务是找到渡轮可以安全穿越海峡的最大时间间隔。

Input Format

输入的第一行包含六个整数：航道数量 $n$ ($1 \leq n \leq 10^5$)，每条航道的宽度 $w$ ($1 \leq w \leq 1,000$)，船只的速度 $u$ 和渡轮的速度 $v$ ($1 \leq u, v \leq 100$)，渡轮最早的出发时间 $t_1$ 和最晚的出发时间 $t_2$ ($0 \leq t_1 < t_2 \leq 10^6$)。所有长度以米为单位，所有速度以米/秒为单位，所有时间以秒为单位。

接下来的 $n$ 行中，每行包含一个航道的数据。每行以 E 或 W 开头，其中 E 表示该航道上的船只向东航行，W 表示向西航行。接下来是一个整数 $m_i$，表示该航道上的船只数量 ($0 \leq m_i \leq 10^5$，对于每个 $1 \leq i \leq n$)。接下来是 $m_i$ 对整数 $l_{ij}$ 和 $p_{ij}$ ($1 \leq l_{ij} \leq 1,000$ 和 $-10^6 \leq p_{ij} \leq 10^6$)。航道 $i$ 上船只 $j$ 的长度为 $l_{ij}$，$p_{ij}$ 是其前端在时间 $0$ 的位置，即其移动方向上的前端。

每条航道内的船只位置相对于渡轮的穿越线。负位置在穿越线的西侧，正位置在东侧。船只不重叠或接触，并按位置递增排序。航道按距离渡轮起点的距离递增排序，渡轮起点在第一条航道的正南方。航道之间没有空隙。船只总数至少为 $1$ 且最多为 $10^5$。

Output Format

显示最大值 $d$，对于某个时间 $s$，渡轮可以在任何时间 $t$ 开始穿越，满足 $s \leq t \leq s+d$。此外，穿越不得早于时间 $t_1$ 开始，且不得晚于时间 $t_2$ 开始。输出的绝对或相对误差必须不超过 $10^{-3}$。你可以假设有一个时间间隔满足 $d > 0.1$ 秒，渡轮可以穿越。

3 100 5 10 0 100
E 2 100 -300 50 -100
W 3 10 60 50 200 200 400
E 1 100 -300

6.00000000

1 100 5 10 0 200
W 4 100 100 100 300 100 700 100 900

50.00000000

Hint

时间限制：3000 毫秒，内存限制：1048576 KB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2015

题面翻译由 ChatGPT-4o 提供。