#P18625. Mirror

Mirror

Mirror

无限二维平面上有一个不透明障碍物和一面单面镜。障碍物是一个三角形;镜子是一条从 (xm,1,ym,1)(x_{m,1},y_{m,1}) 指向 (xm,2,ym,2)(x_{m,2},y_{m,2}) 的有向线段,其右侧具有反射作用。

起点 (x1,y1)(x_1,y_1) 有 mm 块石头。DreamGrid希望将所有石头搬到终点 (x2,y2)(x_2,y_2),并满足:

  • 每次只能携带一块石头;
  • 拿起一块石头后,只能在终点将它放下;
  • 设 LL 是DreamGrid走过的整条路径。对于 LL 上的每一点 pp,DreamGrid都必须能够直接或通过镜子看见所有石头。

还需注意以下具体规则:

  • 如果一条视线的某一部分位于障碍物内部,则不能通过这条视线看见石头。视线经过障碍物的顶点或沿障碍物的边经过是允许的。
  • 若镜子的某个端点位于视线上,则可以通过这个端点直接看见镜子后方,也可以通过镜子反射看见石头。
  • 反射遵循物理定律:入射角等于反射角;入射光线和反射光线位于镜子所在直线的同一侧。
  • 若视线与镜子平行,则不会发生反射,此时镜子也不被视为视线的障碍物。
  • DreamGrid不能走进障碍物内部,但可以在障碍物的边或顶点上移动。
  • DreamGrid不能穿过镜子,但可以在镜子上移动。如果他位于镜子线段的内部(不包括两个端点),他只能看见自己走上镜子时所在的那一侧,不能透过镜子看见另一侧。

请计算将全部石头从起点搬到终点所需行走的最短总距离。

输入格式

第一行包含整数 TT,表示测试用例数。原题描述 TT 约为100。

每个测试用例:

  • 第一行包含整数 mm,表示石头数;
  • 第二行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2;
  • 第三行包含四个整数 xm,1,ym,1,xm,2,ym,2x_{m,1},y_{m,1},x_{m,2},y_{m,2};
  • 接下来三行,每行包含两个整数,分别表示障碍物的三个顶点。

数据范围与保证

  • 1≤m≤1061\le m\le10^6;
  • 所有坐标的绝对值不超过100;
  • 起点和终点均位于障碍物及镜子以外;
  • 镜子与障碍物没有公共点;
  • 输入给出的点中,任意三个点都不共线。

输出格式

每个测试用例输出一行。如果无法在满足全部约束的情况下搬完所有石头,输出-1;否则输出最短总距离。

当且仅当答案的绝对误差或相对误差小于 10−610^{-6} 时,答案被视为正确。

样例输入 1

2
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

样例输出 1

13.416407864999
-1

样例解释

图中的A、B分别表示起点、终点。有向线段 M1→M2M_1\to M_2 表示镜子,右侧为反射面。

第一个样例的原题几何图

第一个测试用例的最优路径为 A→C→B→C→A→C→BA\to C\to B\to C\to A\to C\to B。

第二个样例的原题几何图

第二个测试用例中,在B不能看见A,因此无法在满足题目约束的情况下将两块石头全部搬到B。