#P17888. Euclid in Manhattan
Euclid in Manhattan
平面上的一块矩形区域由横、纵两个方向的分段共同划分。水平方向向右为正,竖直方向向下为正。
横轴依次为住宅段、道路段、住宅段、道路段……住宅段,共有 个住宅段,宽度为 ,相邻住宅段之间的道路宽度为 。
纵轴同样有 个住宅段,高度为 ,相邻住宅段之间的道路宽度为 。
横、纵住宅段相交的矩形为建筑物。路径不能穿过任何建筑物的内部,但允许接触边界和角点。其他位置可以自由移动。
保证任意道路的宽度不大于任意住宅段的宽度或高度。求从整个区域左上角到右下角的最短路径长度,距离采用欧几里得距离。
输入格式
第一行测试用例数 ,。
每组依次输入:
- 两个整数 ,。
- 个整数 。
- 个整数 ,以及行末额外的一个 。
- 个整数 。
- 个整数 ,以及行末额外的一个 。
除两个占位用的行末 外,所有长度均在 。两个占位 必须读入,不代表道路。
若存在道路,满足
$$\max(b_1,\ldots,b_{n-1},d_1,\ldots,d_{m-1})\le\min(a_1,\ldots,a_n,c_1,\ldots,c_m).$$所有测试用例的 之和不超过 。
输出格式
每组输出最短路径长度。绝对误差或相对误差不超过 即可。
样例
2
1 1
1
0
3
0
2 2
3 3
2 0
4 4
3 0
4.0000000000
15.7147766421