PEG Judge - NOI '11 - Intelligent Car Racing

National Olympiad in Informatics, China, 2011

Day 1, Problem 2 - Intelligent Car Racing

The first annual intelligent car competition at JL University has started! The racetrack can be represented as a combination of n rectangular regions (see figure below). The sides of each rectangle are parallel to the axes of the coordinate plane. Rectangle i has its lower left corner at (x_{i, 1}, y_{i, 1}) and upper right corner at (x_{i, 2}, y_{i, 2}).

The following are guaranteed: x_{i, 1} < x_{i, 2} = x_{i+1, 1}, and y_{i, 1} < y_{i, 2}. Neighboring rectangles will always have overlapping edges (indicated by the dotted line below). Intelligent cars can cross over these sections to travel between different rectangular regions.

The contestants must make their self-designed intelligent car travel from a certain starting point S to a certain finishing point T in the shortest time possible. The intelligent car travels at a constant speed of v, where steering does not consume any time, and also cannot travel outside of the racetrack. Can you calculate the fastest time necessary for the car to finish the race?

Input Format

The first line contains a single integer n, representing the number of rectangular regions the racetrack is made up of.
The following n lines will each describe one of these rectangles. The i-th of these lines contains 4 integers x_{i, 1}, y_{i, 1}, x_{i, 2}, and y_{i, 2}, indicating the rectangle i has its lower left corner at (x_{i, 1}, y_{i, 1}) and upper right corner at (x_{i, 2}, y_{i, 2}).
The following line contains two integers x_S and y_S, representing the starting point.
The following line contains two integers x_T and y_T, representing the finishing point.
The last line contains a single real number v (1 ≤ v ≤ 10), representing the speed of the intelligent car.

Output Format

The output should consist of a single real number, accurate to at least 6 digits after the decimal, representing the shortest time in which the intelligent car can complete the race. Your answer will be considered correct if its absolute difference with the correct answer is no greater than 10⁻⁶.