{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere is a non-transparent obstacle and a single-sided mirror in an infinite two-dimensional plane. The obstacle can be represented as a triangle and the mirror can be represented as a \u003cb\u003edirectional\u003c/b\u003e line segment pointing from $(x_{m,1}, y_{m,1})$ to $(x_{m,2}, y_{m,2})$, with the right side being reflective.\u003c/p\u003e\r\n\r\n\u003cp\u003eThere 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:\r\n\r\n\u003c/p\u003e\u003cul\u003e\r\n \u003cli\u003eDreamGrid can only carry one stone each time.\u003c/li\u003e\r\n \u003cli\u003eOnce DreamGrid picks up a stone, he can only put it down at point $(x_2,y_2)$.\u003c/li\u003e\r\n \u003cli\u003eLet $L$ be the path DreamGrid walked, then for each point $p$ on $L$, DreamGrid should see all the stones directly or through the mirror.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003cp\u003eNote that:\r\n\u003c/p\u003e\u003cul\u003e\r\n \u003cli\u003eIf some part of the line vision is inside the obstacle (it\u0027s ok that the line vision passes a point or edge of the obstacle), it\u0027s considered, that DreamGrid cannot see the stone with this line of vision.\u003c/li\u003e\r\n \u003cli\u003eIf one of the two endpoints of the mirror is on the line of vision, it\u0027s considered, that DreamGrid can see the stone both in the mirror and through the mirror.\u003c/li\u003e\r\n \u003cli\u003eThe reflection process is governed by laws of physics --- the angle of incidence is equal to the angle of reflection. The incident ray is in the same half-plane as the reflected ray, relative to the mirror.\u003c/li\u003e\r\n \u003cli\u003eIf the line of vision is parallel to the mirror, reflection doesn\u0027t take place, and the mirror isn\u0027t regarded as an obstacle.\u003c/li\u003e\r\n \u003cli\u003eDreamGrid cannot move into the obstacle but can move on the edges or the vertices of the obstacle.\u003c/li\u003e\r\n \u003cli\u003eDreamGrid cannot move through the mirror but can move on the mirror. Note that if DreamGrid is on the line segment of the mirror other than the two endpoints, he can only see the side he comes from, and cannot see through the mirror.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003cp\u003e\u003c/p\u003e\r\n\r\n\u003cp\u003eDreamGrid would like to know the shortest distance to move all stones from $(x_1,y_1)$ to $(x_2, y_2)$.\u003c/p\u003e\r\n\r\n\u003ch4\u003eInput\u003c/h4\u003e\r\n\u003cp\u003eThere 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:\u003c/p\u003e\r\n\r\n\u003cp\u003eThe first line contains one integer $m$ ($1 \\le m \\le 10^6$), indicating the number of stones.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe second line contains four integers $x_1$, $y_1$, $x_2$ and $y_2$, indicating the start point and the target point.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe third line contains four integers $x_{m,1}$, $y_{m,1}$, $x_{m,2}$ and $y_{m,2}$, indicating the coordinates of the mirror.\u003c/p\u003e\r\n\r\n\u003cp\u003eEach of the next $3$ lines has two integers $x_i$ and $y_i$, indicating the coordinates of the vertices of the obstacle.\u003c/p\u003e\r\n\r\n\u003cp\u003eAll 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.\u003c/p\u003e\r\n\r\n\u003cp\u003eIt is guaranteed that no three points are collinear.\u003c/p\u003e\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\u003cp\u003eFor each test case, output a real number indicating the shortest distance, or output $-1$ if DreamGrid cannot move all the stones under the constraints.\u003c/p\u003e\r\n\r\n\u003cp\u003eYour answer will be considered correct if and only if the absolute error or relative error of your answer is less than $10^{-6}$.\u003c/p\u003e\r\n\r\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2\r\n-2 0 2 0\r\n-3 3 3 3\r\n0 1\r\n-3 -2\r\n3 -2\r\n2\r\n-2 0 2 0\r\n-3 3 -1 3\r\n0 1\r\n-3 -2\r\n3 -2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13.416407864998739\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003ch4\u003eHint\u003c/h4\u003e\r\n\u003cp\u003eWe now welcome our special guest Mashiro, who heartily donates this problem to our problemset, to\r\nexplain the sample test cases for us using her sketch book.\u003c/p\u003e\r\n\r\n\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/c1bcfaf5fff544f32a5afc3715882d22?v\u003d1715947508\" style\u003d\"width: 400px; margin-right: 20px\"\u003e\u003cimg src\u003d\"CDN_BASE_URL/07004b9b174e830faca5403e605d2e04?v\u003d1715947508\" style\u003d\"width: 400px; margin-left: 20px\"\u003e\u003c/center\u003e\r\n\r\n\u003cimg src\u003d\"CDN_BASE_URL/34359a7e51503e9f8607d0da90f3f18e?v\u003d1715947508\" style\u003d\"width: 200px; float: right; margin: 20px\"\u003e\u003cbr\u003e\u003cbr\u003e\r\n\r\n\u003cp\u003eIn 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.\u003c/p\u003e\r\n\r\n\u003cp\u003eFor the first sample test case, the optimal path is $A \\to C \\to B \\to C \\to A \\to C \\to B$.\u003c/p\u003e\r\n\r\n\u003cp\u003eFor the second sample test case, as DreamGrid cannot see $A$ from $B$, it\u0027s impossible to move all the two stones from $A$ to $B$ while following the constraints in the problem description.\u003c/p\u003e\r\n"}}]}