Humanity's Last Code Exam / 2015_I / Ship Traffic

## Problem Description

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. Your task is to find the largest time interval within which the ferry can safely cross the strait.

## Input

The first line of input contains six integers: 

- n (1 ≤ n ≤ 100,000): the number of lanes
- w (1 ≤ w ≤ 1,000): the width of each lane
- u: the speed of ships
- v: the speed of the ferry (1 ≤ u,v ≤ 100)
- t₁: the ferry’s earliest start time
- t₂: the ferry’s latest start time (0 ≤ t₁ < t₂ ≤ 1,000,000)

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 ≤ m_(i) ≤ 100,000 for each 1 ≤ i ≤ n). It is followed by m_(i) pairs of integers l_(ij) and p_(ij) (1 ≤ l_(ij) ≤ 1,000 and -1,000,000 ≤ p_(ij) ≤ 1,000,000). 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 100,000.

## Output

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≤t≤s+d. Additionally, the crossing must not start before time t₁ and must start no later than time t₂. 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.

## Sample Input and Output

### Sample Input 1

## Problem Description

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. Your task is to find the largest time interval within which the ferry can safely cross the strait.

## Input

The first line of input contains six integers: 

- \( n \) (1 ≤ \( n \) ≤ 100,000): the number of lanes
- \( w \) (1 ≤ \( w \) ≤ 1,000): the width of each lane
- \( u \): the speed of ships
- \( v \): the speed of the ferry (1 ≤ \( u, v \) ≤ 100)
- \( t_1 \): the ferry’s earliest start time
- \( t_2 \): the ferry’s latest start time (0 ≤ \( t_1 \) < \( t_2 \) ≤ 1,000,000)

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 ≤ \( m_i \) ≤ 100,000 for each 1 ≤ \( i \) ≤ \( n \)). It is followed by \( m_i \) pairs of integers \( l_{ij} \) and \( p_{ij} \) (1 ≤ \( l_{ij} \) ≤ 1,000 and -1,000,000 ≤ \( p_{ij} \) ≤ 1,000,000). 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 100,000.

## Output

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.

## Sample Input and Output

### Sample Input 1