#P18625. Mirror
Mirror
Mirror
无限二维平面上有一个不透明障碍物和一面单面镜。障碍物是一个三角形;镜子是一条从 指向 的有向线段,其右侧具有反射作用。
起点 有 块石头。DreamGrid希望将所有石头搬到终点 ,并满足:
- 每次只能携带一块石头;
- 拿起一块石头后,只能在终点将它放下;
- 设 是DreamGrid走过的整条路径。对于 上的每一点 ,DreamGrid都必须能够直接或通过镜子看见所有石头。
还需注意以下具体规则:
- 如果一条视线的某一部分位于障碍物内部,则不能通过这条视线看见石头。视线经过障碍物的顶点或沿障碍物的边经过是允许的。
- 若镜子的某个端点位于视线上,则可以通过这个端点直接看见镜子后方,也可以通过镜子反射看见石头。
- 反射遵循物理定律:入射角等于反射角;入射光线和反射光线位于镜子所在直线的同一侧。
- 若视线与镜子平行,则不会发生反射,此时镜子也不被视为视线的障碍物。
- DreamGrid不能走进障碍物内部,但可以在障碍物的边或顶点上移动。
- DreamGrid不能穿过镜子,但可以在镜子上移动。如果他位于镜子线段的内部(不包括两个端点),他只能看见自己走上镜子时所在的那一侧,不能透过镜子看见另一侧。
请计算将全部石头从起点搬到终点所需行走的最短总距离。
输入格式
第一行包含整数 ,表示测试用例数。原题描述 约为100。
每个测试用例:
- 第一行包含整数 ,表示石头数;
- 第二行包含四个整数 ;
- 第三行包含四个整数 ;
- 接下来三行,每行包含两个整数,分别表示障碍物的三个顶点。
数据范围与保证
- ;
- 所有坐标的绝对值不超过100;
- 起点和终点均位于障碍物及镜子以外;
- 镜子与障碍物没有公共点;
- 输入给出的点中,任意三个点都不共线。
输出格式
每个测试用例输出一行。如果无法在满足全部约束的情况下搬完所有石头,输出-1;否则输出最短总距离。
当且仅当答案的绝对误差或相对误差小于 时,答案被视为正确。
样例输入 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分别表示起点、终点。有向线段 表示镜子,右侧为反射面。

第一个测试用例的最优路径为 。

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