题目描述

Ferries crossing the Strait of Gibraltar from Morocco to Spain must carefully navigate to avoid the heavy ship traffic along the strait. Write a program to help ferry captains find the largest gaps in strait traffic for a safe crossing.

Your program will use a simple model as follows. The strait has several parallel shipping lanes in east-west direction. Ships run with the same constant speed either eastbound or westbound. All ships in the same lane run in the same direction. Satellite data provides the positions of the ships in each lane. The ships may have different lengths. Ships do not change lanes and do not change speed for the crossing ferry.

The ferry waits for an appropriate time when there is an adequate gap in the ship traffic. It then crosses the strait heading northbound along a north-south line at a constant speed. From the moment a ferry enters a lane until the moment it leaves the lane, no ship in that lane may touch the crossing line. Ferries are so small you can neglect their size. Figure 1 illustrates the lanes and ships for Sample Input 1. Your task is to find the largest time interval within which the ferry can safely cross the strait.

Figure 1: Sample Input 1.

输入格式

The first line of input contains six integers: the number of lanes $n$ ($1 \leq n \leq 10^5$), the width $w$ of each lane ($1 \leq w \leq 1\, 000$), the speed $u$ of ships and the speed $v$ of the ferry ($1 \leq u, v \leq 100$), the ferry’s earliest start time $t_1$ and the ferry’s latest start time $t_2$ ($0 \leq t_1 < t_2 \leq 10^6$). All lengths are given in meters, all speeds are given in meters/second, and all times are given in seconds.

Each of the next $n$ lines contains the data for one lane. Each line starts with either E or W, where E indicates that ships in this lane are eastbound and W indicates that ships in this lane are westbound. Next in the line is an integer $m_ i$, the number of ships in this lane ($0 \leq m_ i \leq 10^5$ for each $1 \leq i \leq n$). It is followed by $m_ i$ pairs of integers $l_{ij}$ and $p_{ij}$ ($1 \leq l_{ij} \leq 1\, 000$ and $-10^6 \leq p_{ij} \leq 10^6$). The length of ship $j$ in lane $i$ is $l_{ij}$, and $p_{ij}$ is the position at time $0$ of its forward end, that is, its front in the direction it moves.

Ship positions within each lane are relative to the ferry’s crossing line. Negative positions are west of the crossing line and positive positions are east of it. Ships do not overlap or touch, and are sorted in increasing order of their positions. Lanes are ordered by increasing distance from the ferry’s starting point, which is just south of the first lane. There is no space between lanes. The total number of ships is at least $1$ and at most $10^5$.

输出格式

Display the maximal value $d$ for which there is a time $s$ such that the ferry can start a crossing at any time $t$ with $s \leq t \leq s+d$. Additionally the crossing must not start before time $t_1$ and must start no later than time $t_2$. The output must have an absolute or relative error of at most $10^{-3}$. You may assume that there is a time interval with $d > 0.1$ seconds for the ferry to cross.

题目大意

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

您的程序将使用一个简单的模型，如下所示：海峡有几条东西方向的平行航道。船舶以相同的恒定速度向东或向西行驶。同一航道上的所有船只都朝同一方向行驶。卫星数据提供了每条水道上船只的位置。这些船可能有不同的长度。船舶不会改变航道，也不会改变过境渡轮的速度。

当船舶交通有足够的间隙时，渡轮会等待适当的时间。然后它以恒定的速度沿着南北线向北行驶穿过海峡。从渡轮进入水道的那一刻起，直到它离开水道的那一刻，该水道上的船只都不得触碰过界线。渡轮很小，所以你可以忽略它们的长度。您的任务是找到渡轮可以安全穿越海峡的最大时间间隔。

输入的第一行包含六个整数：水道数$n$($1≤n≤10^5$)，每条水道的宽度$w$($1≤w≤1000$)，船速$u$和渡船速度$v$ ($1≤u,v≤100$)，渡轮的最早开始时间$t1$和渡轮的最晚开始时间$t2$($0≤t1<t2≤10^6$)。所有长度均以米为单位，所有速度均以米/秒为单位，所有时间均以秒为单位。

接下来的$n$行中的每一行都包含一条水道的数据。每行以 E 或 W 开头，其中 E 表示此车道中的船舶向东行驶，W 表示此水道中的船舶向西行驶。行中的下一个是整数$m_i$，表示这条航线上的船只数量($0≤m_i≤10^5$ for each $1≤i≤n$)。 紧随其后的是$m_i$对$l_{ij}$和 $p_{ij}$($1≤l_{ij}≤1000$ and $-10^6≤p_{ij}≤10^6$)。$l_{ij}$表示船$j$在车道$i$上的长度，$p_{ij}$是其前端在时间$0$的位置，即其前方在其移动方向上的位置。

每条车道内的船舶位置相对于渡轮的交叉线。负仓位位于交叉线以西，正仓位位于交叉线以东。船只不重叠或接触，并按其位置的递增顺序排序。车道的顺序是增加与渡轮起点的距离，该起点位于第一条车道的南边。车道之间没有空间。船舶总数至少为 $1$，最多$10^5$。

输出存在于时间$s$的最大值$d$，以便渡船可以在任何时间t开始穿越海峡且$s≤t≤s+d$. 此外，横渡不得在时间$t1$之前开始，并且不得晚于时间$t2$开始。输出的绝对或相对误差必须最多为$10^{-3}$。您可以假设渡轮通过的时间间隔为$d$（$d>0.1$） 秒。

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

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

提示

Time limit: 3000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2015