
ZOJ Problem Set  4065
There is a nontransparent obstacle and a singlesided mirror in an infinite twodimensional plane. The obstacle can be represented as a triangle and the mirror can be represented as a directional line segment pointing from $(x_{m,1}, y_{m,1})$ to $(x_{m,2}, y_{m,2})$, with the right side being reflective. There are $m$ stones at point $(x_1,y_1)$ and DreamGrid would like to move all the stones to point $(x_2,y_2)$. The following constraints must be satisfied:
Note that:
DreamGrid would like to know the shortest distance to move all stones from $(x_1,y_1)$ to $(x_2, y_2)$. InputThere are multiple test cases. The first line of input is an integer $T$ (about 100), indicates the number of test cases. For each test case: The first line contains one integer $m$ ($1 \le m \le 10^6$), indicating the number of stones. The second line contains four integers $x_1$, $y_1$, $x_2$ and $y_2$, indicating the start point and the target point. The third line contains four integers $x_{m,1}$, $y_{m,1}$, $x_{m,2}$ and $y_{m,2}$, indicating the coordinates of the mirror. Each of the next $3$ lines has two integers $x_i$ and $y_i$, indicating the coordinates of the vertices of the obstacle. All the coordinates will not exceed $100$ in absolute value. Both the start point and target point are outside the obstacle and the mirror. The mirror and the obstacle have no points in common. It is guaranteed that no three points are collinear. OutputFor each test case, output a real number indicating the shortest distance, or output $1$ if DreamGrid cannot move all the stones under the constraints. Your answer will be considered correct if and only if the absolute error or relative error of your answer is less than $10^{6}$. Sample Input2 2 2 0 2 0 3 3 3 3 0 1 3 2 3 2 2 2 0 2 0 3 3 1 3 0 1 3 2 3 2 Sample Output13.416407864998739 1 HintWe now welcome our special guest Mashiro, who heartily donates this problem to our problemset, to explain the sample test cases for us using her sketch book. In the figures above, we indicate the start point as point $A$ and the target point as point $B$. The mirror is indicated by the line segment pointing from $M1$ to $M2$, with the right side being reflective. For the first sample test case, the optimal path is $A \to C \to B \to C \to A \to C \to B$. For the second sample test case, as DreamGrid cannot see $A$ from $B$, it's impossible to move all the two stones from $A$ to $B$ while following the constraints in the problem description. Author: JIN, Mengge; LIN, Xi Source: The 2018 ACMICPC Asia Qingdao Regional Contest 