P1995 [NOI2011] Smart Car Competition

A new Intelligent Vehicle contest has begun at JL University! The race track can be regarded as being formed by $n$ rectangular regions stitched together (as shown in the figure below). Each rectangle has sides parallel to the coordinate axes. For the $i$-th rectangle, the lower-left and upper-right corners are $(x_{i,1}, y_{i,1})$ and $(x_{i,2}, y_{i,2})$, respectively. It is guaranteed that $x_{i,1} < x_{i,2} = x_{i+1,1}$ and $y_{i,1} < y_{i,2}$. Any two adjacent rectangles share an overlapping edge segment (as indicated by the dashed line in the figure), and the smart car can move between rectangles through this overlap.  Participants must drive their designed smart car from a given start point $S$ to a given end point $T$ in the shortest possible time, without leaving the track. Assume the car’s speed is a constant $v$, and turning takes no time. Can you compute the minimum time needed to finish the race?

The first line contains a positive integer $n$, the number of rectangles that make up the track. The next $n$ lines describe the rectangles. The $i$-th of these lines contains $4$ integers $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}$, denoting that the lower-left and upper-right corners of the $i$-th rectangle are $(x_{i,1}, y_{i,1})$ and $(x_{i,2}, y_{i,2})$, respectively. The next line contains two integers $x_S, y_S$, the coordinates of the start point. The next line contains two integers $x_T, y_T$, the coordinates of the end point. The next line contains a real number $v$, the speed of the smart car.

Output a single real number, the minimum time for the smart car to finish the race, accurate to at least six digits after the decimal point. For each test point, if your output differs from the reference answer by no more than $10^{-6}$, you will receive full credit for that test point; otherwise, you will receive no credit.

 Translated by ChatGPT 5