National Olympiad in Informatics, China, 2011
The first annual intelligent car competition at JL University has started! The racetrack can be represented as a combination of rectangular regions (see figure below). The sides of each rectangle are parallel to the axes of the coordinate plane. Rectangle has its lower left corner at and upper right corner at .
The following are guaranteed: , and . 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 to a certain finishing point in the shortest time possible. The intelligent car travels at a constant speed of , 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 Specification
The first line contains a single integer , representing the number of
rectangular regions the racetrack is made up of.
The following lines will each describe one of these rectangles. The
-th of these lines contains integers , , ,
and , indicating the rectangle has its lower left
corner at and upper right corner at .
The following line contains two integers and ,
representing the starting point.
The following line contains two integers and ,
representing the finishing point.
The last line contains a single real number ,
representing the speed of the intelligent car.
Output Specification
The output should consist of a single real number, accurate to at least 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 .
Sample Input
2
1 1 2 2
2 0 3 4
1 1
3 0
1.0
Sample Output
2.41421356
Constraints
The attributes of all the test cases are outlined below.
Test Case | Range of | Range of Coordinates |
---|---|---|
All coordinates will be integers with absolute values not exceeding . | ||
Problem translated to English by .
Comments