#P17888. Euclid in Manhattan

Euclid in Manhattan

平面上的一块矩形区域由横、纵两个方向的分段共同划分。水平方向向右为正,竖直方向向下为正。

横轴依次为住宅段、道路段、住宅段、道路段……住宅段,共有 nn 个住宅段,宽度为 a1,…,ana_1,\ldots,a_n,相邻住宅段之间的道路宽度为 b1,…,bn−1b_1,\ldots,b_{n-1}。

纵轴同样有 mm 个住宅段,高度为 c1,…,cmc_1,\ldots,c_m,相邻住宅段之间的道路宽度为 d1,…,dm−1d_1,\ldots,d_{m-1}。

横、纵住宅段相交的矩形为建筑物。路径不能穿过任何建筑物的内部,但允许接触边界和角点。其他位置可以自由移动。

保证任意道路的宽度不大于任意住宅段的宽度或高度。求从整个区域左上角到右下角的最短路径长度,距离采用欧几里得距离。

输入格式

第一行测试用例数 tt,1≤t≤1001\le t\le100。

每组依次输入:

  1. 两个整数 n,mn,m,1≤n,m≤20001\le n,m\le2000。
  2. nn 个整数 a1,…,ana_1,\ldots,a_n。
  3. n−1n-1 个整数 b1,…,bn−1b_1,\ldots,b_{n-1},以及行末额外的一个 00。
  4. mm 个整数 c1,…,cmc_1,\ldots,c_m。
  5. m−1m-1 个整数 d1,…,dm−1d_1,\ldots,d_{m-1},以及行末额外的一个 00。

除两个占位用的行末 00 外,所有长度均在 [1,106][1,10^6]。两个占位 00 必须读入,不代表道路。

若存在道路,满足

$$\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).$$

所有测试用例的 nmnm 之和不超过 4×1064\times10^6。

输出格式

每组输出最短路径长度。绝对误差或相对误差不超过 10−910^{-9} 即可。

样例

2
1 1
1
0
3
0
2 2
3 3
2 0
4 4
3 0
4.0000000000
15.7147766421