410672: GYM104072 J Spaceship

Your mom was cleaning the house and she found your old Nintendo console back from the 90s when you were just a kid. You remember that you used to like the "Spaceship" game so much that you started playing it again.

The game is played on the 2D plane and consists of a spaceship that starts in the point $$$(X_{start}, Y_{start})$$$ and has to get to the point $$$(X_{finish}, Y_{finish})$$$. We consider the spaceship a single point in a plane with area 0. You can move the spaceship in any direction (ex: it can also curve) but only towards the right (i.e., the $$$X$$$ coordinate can never decrease). On the plane there are $$$N$$$ segments sorted from left to right. That is, $$$X_{start} < X^1_1 < X^2_1 < X^1_2 < X^2_2 < ... < X^1_N < X^2_N < X_{finish}$$$, where $$$(X^1_i, Y^1_i)$$$ and $$$(X^2_i, Y^2_i)$$$ are the ends of the $$$i^{\text{th}}$$$ segment ($$$1 \leq i \leq N$$$). Each segment is of one of the following two types:

• Wall: The spaceship cannot pass through the interior points of this segment (i.e., it is allowed to pass through the two ends of the segment). However, the spaceship is allowed to move along the segment
• Magic gate: If the spaceship passes through this segment (including its ends), you earn $$$P_i$$$ magic points. You can earn the $$$P_i$$$ points for this segment only once no matter how many times you pass through it

The final score of the game is the total distance traversed by the spaceship minus the total magic points accumulated. The goal of the game is to minimize the score. Because we are now in the $$$21^{\text{st}}$$$ century, you decide to write a program to compute the minimum score to move the spaceship from $$$(X_{start}, Y_{start})$$$ to $$$(X_{finish}, Y_{finish})$$$.

The first line of the input contains the integer $$$N$$$ ($$$1 \leq N \leq 2000$$$), denoting the number of segments. Each of the following $$$N$$$ lines contains an integer $$$type_i$$$ ($$$0 \leq type_i \leq 1$$$). If $$$type_i = 0$$$, then this segment is a Wall. If $$$type_i = 1$$$, then this segment is a Magic gate and the next integer in the input line is $$$P_i$$$ ($$$0 \leq P_i \leq 10^9$$$), denoting the magic points corresponding to this segment. In both cases, the input line contains $$$4$$$ more integers $$$X^1_i, Y^1_i, X^2_i, Y^2_i$$$ ($$$0 \leq X^1_i, Y^1_i, X^2_i, Y^2_i \leq 10^9$$$), denoting the ends of this segment. The last line of the input contains 4 integers $$$X_{start}, Y_{start}, X_{finish}, Y_{finish}$$$ ($$$0 \leq X_{start}, Y_{start}, X_{finish}, Y_{finish} \leq 10^9$$$), denoting the start point and the finish point.

Among all the $$$2 * (N + 1)$$$ points from the input, there aren't any $$$3$$$ collinear points.

On a single line, print the minimum score to move the spaceship from $$$(X_{start}, Y_{start})$$$ to $$$(X_{finish}, Y_{finish})$$$. Your answer will be considered correct if the absolute or relative difference between your answer and judge's answer is less than $$$10^{-8}$$$.

3
0 2 3 3 5
1 3 4 1 5 2
0 6 1 7 8
1 3 9 6

8.216116701980

The picture bellow corresponds to the example. The red segments are walls and the green segments are magic gates. The optimal path for the spaceship is to move in a straight line from the start point $$$(1, 3)$$$ to point $$$(6, 1)$$$, and from there in a straight line to the finish point $$$(9, 6)$$$. This path does not pass through any wall. Also, it passes through the magic gate from which we earn $$$3$$$ points. The score of the path is $$$\sqrt{29} + \sqrt{34} - 3$$$, and this is the minimum possible score.