{"problem":{"name":"[ICPC 2018 Qingdao R] Mirror","description":{"content":"There 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 $\\textbf{direct","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":15000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9892"},"statements":[{"statement_type":"Markdown","content":"There 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 $\\textbf{directional}$ line segment pointing from $(x_{m,1}, y_{m,1})$ to $(x_{m,2}, y_{m,2})$, with the right side being reflective.\n\nThere 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:\n\n- DreamGrid can only carry one stone each time.\n- Once DreamGrid picks up a stone, he can only put it down at point $(x_2,y_2)$.\n- Let $L$ be the path DreamGrid walked, then for each point $p$ on $L$, DreamGrid should see all the stones directly or through the mirror.\n\nNote that:\n\n- If some part of the line vision is inside the obstacle (it's ok that the line vision passes a point or edge of the obstacle), it's considered, that DreamGrid cannot see the stone with this line of vision.\n- If one of the two endpoints of the mirror is on the line of vision, it's considered, that DreamGrid can see the stone both in the mirror and through the mirror.\n- The 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.\n- If the line of vision is parallel to the mirror, reflection doesn't take place, and the mirror isn't regarded as an obstacle.\n- DreamGrid cannot move into the obstacle but can move on the edges or the vertices of the obstacle.\n- DreamGrid 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.\n\nDreamGrid would like to know the shortest distance to move all stones from $(x_1,y_1)$ to $(x_2, y_2)$.\n\n## Input\n\nThere 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:\n\nThe first line contains one integer $m$ ($1 \\le m \\le 10^6$), indicating the number of stones.\n\nThe second line contains four integers $x_1$, $y_1$, $x_2$ and $y_2$, indicating the start point and the target point.\n\nThe third line contains four integers $x_{m,1}$, $y_{m,1}$, $x_{m,2}$ and $y_{m,2}$, indicating the coordinates of the mirror.\n\nEach of the next $3$ lines has two integers $x_i$ and $y_i$, indicating the coordinates of the vertices of the obstacle.\n\nAll 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.\n\nIt is guaranteed that no three points are collinear.\n\n## Output\n\nFor each test case, output a real number indicating the shortest distance, or output $-1$ if DreamGrid cannot move all the stones under the constraints.\n\nYour answer will be considered correct if and only if the absolute error or relative error of your answer is less than $10^{-6}$.\n\n[samples]\n\n## Note\n\nWe 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.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/wsxbrf43.png)\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/d2bpz78p.png)\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/nfhakntz.png)\n\n$\\textit{(Image from pixiv. ID: 32084305)}$\n\nIn 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.\n\nFor the first sample test case, the optimal path is $A \\to C \\to B \\to C \\to A \\to C \\to B$.\n\nFor 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.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9892","tags":["计算几何","2018","Special Judge","O2优化","ICPC","青岛"],"sample_group":[["2\n2\n-2 0 2 0\n-3 3 3 3\n0 1\n-3 -2\n3 -2\n2\n-2 0 2 0\n-3 3 -1 3\n0 1\n-3 -2\n3 -2","13.416407864999\n-1"]],"created_at":"2026-03-03 11:09:25"}}