DreamGrid's Stone Transfer

There is a non-transparent obstacle and a single-sided mirror in an infinite two-dimensional plane. The obstacle is represented as a triangle and the mirror is represented as a directional line segment from \( (x_{m,1}, y_{m,1}) \) to \( (x_{m,2}, y_{m,2}) \), with the reflective side on the right.

There are \( m \) stones located at point \( (x_1, y_1) \) that need to be moved to point \( (x_2, y_2) \). DreamGrid can only carry one stone at a time and, once a stone is picked up, it must be deposited at \( (x_2, y_2) \).

Furthermore, let \( L \) be the path taken by DreamGrid. For each point \( p \) on \( L \), DreamGrid must be able to see all the stones, either directly or via the mirror reflection. The reflection obeys the law of reflection, i.e., the angle of incidence is equal to the angle of reflection, with the incident ray and the reflected ray lying in the same half-plane relative to the mirror.

Note the following:

• If any part of the line of vision enters the interior of the obstacle (even though it may touch an edge or vertex), that stone is considered not visible.
• If an endpoint of the mirror is exactly on the line of vision, it is considered that DreamGrid can see the stone both directly and through the mirror.
• If the line of vision is parallel to the mirror, no reflection occurs and the mirror is not considered as an obstruction.
• DreamGrid cannot enter the interior of the obstacle but may move along its edges or vertices.
• DreamGrid cannot cross the mirror, although he may move along it. (Note: if DreamGrid is on the mirror (but not at an endpoint), he can only see in the direction from which he came and cannot see through the mirror.)

Your task is to compute the shortest distance that DreamGrid must travel in order to move all the stones from \( (x_1, y_1) \) to \( (x_2, y_2) \).

Note: For the purpose of this problem, you may assume that the input guarantees that a straight line path from \( (x_1, y_1) \) to \( (x_2, y_2) \) satisfies the visibility constraints. In this simplified model, the answer is computed as \( m \) times the Euclidean distance between \( (x_1, y_1) \) and \( (x_2, y_2) \).

inputFormat

The input consists of four lines:

1. An integer \( m \) (\(1 \le m \le 10^5\)) representing the number of stones.
2. Four real numbers \( x_1\ y_1\ x_2\ y_2 \) representing the coordinates of the stone's initial position and destination.
3. Four real numbers \( x_{m,1}\ y_{m,1}\ x_{m,2}\ y_{m,2} \) representing the coordinates of the mirror's endpoints. The mirror points from \( (x_{m,1}, y_{m,1}) \) to \( (x_{m,2}, y_{m,2}) \), with the right side being reflective.
4. Six real numbers representing the coordinates of the triangle's vertices: \( x_a\ y_a\ x_b\ y_b\ x_c\ y_c \).

outputFormat

Output a single real number: the shortest distance that DreamGrid must travel to move all the stones. The answer is considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

3
0 0 3 4
-1 -1 1 1
2 0 2 2 0 2

15.0000000000