题目 2595:
蓝桥杯2020年第十一届国赛真题-出租车
时间限制: 3s
内存限制: 192MB 提交: 70 解决: 4
题目描述
小蓝在 L 市开出租车。
L 市的规划很规整，所有的路都是正东西向或者正南北向的，道路都可以看成直线段。东西向的道路互相平行，南北向的道路互相平行，任何一条东西向道路垂直于任何一条南北向道路。
从北到南一共有 n 条东西向道路，依次标号为 H 1 , H 2 , ···, H n 。从西到东一共有 m 条南北向的道路，依次标号为 S 1 , S 2 , ···, S m 。每条道路都有足够长，每一条东西向道路和每一条南北向道路都相交，H i与 S j 的交叉路口记为 (i, j)。从 H 1 和 S 1 的交叉路口 (1,1) 开始，向南遇到的路口与 (1,1) 的距离分别是 h 1 , h 2 , ···, h n−1 ，向东遇到路口与 (1,1) 的距离分别是 w 1 , w 2 , ···, w m−1 。道路的每个路口都有一个红绿灯。时刻 0 的时候，南北向绿灯亮，东西向红灯亮，南北向的绿灯会持续一段
时间（每个路口不同），然后南北向变成红灯，东西向变成绿灯，持续一段时间后，再变成南北向绿灯，东西向红灯。
已知路口 (i, j) 的南北向绿灯每次持续的时间为 g ij ，东西向的绿灯每次持续的时间为 r ij ，红绿灯的变换时间忽略。
当一辆车走到路口时，如果是绿灯，可以直行、左转或右转。如果是红灯，可以右转，不能直行或左转。如果到路口的时候刚好由红灯变为绿灯，则视为
看到绿灯，如果刚好由绿灯变为红灯，则视为看到红灯。每段道路都是双向道路，道路中间有隔离栏杆，在道路中间不能掉头，只能在红绿灯路口掉头。掉头时不管是红灯还是绿灯都可以直接掉头。掉头的时间可以忽略。小蓝时刻 0 从家出发。今天，他接到了 q 个预约的订单，他打算按照订单的顺序依次完成这些订单，就回家休息。中途小蓝不准备再拉其他乘客。
小蓝的家在两个路口的中点，小蓝喜欢用 x 1 , y 1 , x 2 , y 2 来表示自己家的位置，即路口 (x 1 ,y 1 ) 到路口 (x 2 ,y 2 ) 之间的道路中点的右侧，保证两个路口相邻（中间没有其他路口）。请注意当两个路口交换位置时，表达的是路的不同两边，路中间有栏杆，因此这两个位置实际要走比较远才能到达。小蓝的订单也是从某两个路口间的中点出发，到某两个路口间的中点结束。小蓝必须按照给定的顺序处理订单，而且一个时刻只能处理一个订单，不能图省时间而同时接两位乘客，也不能插队完成后面的订单。小蓝只对 L 市比较熟，因此他只会在给定的 n 条东西向道路和 m 条南北向道路上行驶，而且不会驶出 H 1 , H n , S 1 , S m 这几条道路所确定的矩形区域（可以到边界）。小蓝行车速度一直为 1，乘客上下车的时间忽略不计。请问，小蓝最早什么时候能完成所有订单回到家。
L 市的规划很规整，所有的路都是正东西向或者正南北向的，道路都可以看成直线段。东西向的道路互相平行，南北向的道路互相平行，任何一条东西向道路垂直于任何一条南北向道路。
从北到南一共有 n 条东西向道路，依次标号为 H 1 , H 2 , ···, H n 。从西到东一共有 m 条南北向的道路，依次标号为 S 1 , S 2 , ···, S m 。每条道路都有足够长，每一条东西向道路和每一条南北向道路都相交，H i与 S j 的交叉路口记为 (i, j)。从 H 1 和 S 1 的交叉路口 (1,1) 开始，向南遇到的路口与 (1,1) 的距离分别是 h 1 , h 2 , ···, h n−1 ，向东遇到路口与 (1,1) 的距离分别是 w 1 , w 2 , ···, w m−1 。道路的每个路口都有一个红绿灯。时刻 0 的时候，南北向绿灯亮，东西向红灯亮，南北向的绿灯会持续一段
时间（每个路口不同），然后南北向变成红灯，东西向变成绿灯，持续一段时间后，再变成南北向绿灯，东西向红灯。
已知路口 (i, j) 的南北向绿灯每次持续的时间为 g ij ，东西向的绿灯每次持续的时间为 r ij ，红绿灯的变换时间忽略。
当一辆车走到路口时，如果是绿灯，可以直行、左转或右转。如果是红灯，可以右转，不能直行或左转。如果到路口的时候刚好由红灯变为绿灯，则视为
看到绿灯，如果刚好由绿灯变为红灯，则视为看到红灯。每段道路都是双向道路，道路中间有隔离栏杆，在道路中间不能掉头，只能在红绿灯路口掉头。掉头时不管是红灯还是绿灯都可以直接掉头。掉头的时间可以忽略。小蓝时刻 0 从家出发。今天，他接到了 q 个预约的订单，他打算按照订单的顺序依次完成这些订单，就回家休息。中途小蓝不准备再拉其他乘客。
小蓝的家在两个路口的中点，小蓝喜欢用 x 1 , y 1 , x 2 , y 2 来表示自己家的位置，即路口 (x 1 ,y 1 ) 到路口 (x 2 ,y 2 ) 之间的道路中点的右侧，保证两个路口相邻（中间没有其他路口）。请注意当两个路口交换位置时，表达的是路的不同两边，路中间有栏杆，因此这两个位置实际要走比较远才能到达。小蓝的订单也是从某两个路口间的中点出发，到某两个路口间的中点结束。小蓝必须按照给定的顺序处理订单，而且一个时刻只能处理一个订单，不能图省时间而同时接两位乘客，也不能插队完成后面的订单。小蓝只对 L 市比较熟，因此他只会在给定的 n 条东西向道路和 m 条南北向道路上行驶，而且不会驶出 H 1 , H n , S 1 , S m 这几条道路所确定的矩形区域（可以到边界）。小蓝行车速度一直为 1，乘客上下车的时间忽略不计。请问，小蓝最早什么时候能完成所有订单回到家。
输入格式
输入第一行包含两个整数 n, m，表示东西向道路的数量和南北向道路的数量。
第二行包含 n − 1 个整数 h 1 , h 2 , ···, h n−1 。
第三行包含 m − 1 个整数 w 1 , w 2 , ···, w m−1 。
接下来 n 行，每行 m 个整数，描述每个路口南北向绿灯的时间，其中的第i 行第 j 列表示 g ij 。
接下来 n 行，每行 m 个整数，描述每个路口东西向绿灯的时间，其中的第i 行第 j 列表示 r ij 。
接下来一行包含四个整数 x 1 , y 1 , x 2 , y 2 ，表示小蓝家的位置在路口 (x 1 ,y 1 )到路口 (x 2 ,y 2 ) 之间的道路中点的右侧。
接下来一行包含一个整数 q，表示订单数量。
接下来 q 行，每行描述一个订单，其中第 i 行包含八个整数 x i1 , y i1 , x i2 , y i2 ,x i3 , y i3 , x i4 , y i4 ，表示第 i 个订单的起点为路口 (x i1 ,y i1 ) 到路口 (x i2 ,y i2 ) 之间的道路中点的右侧，第 i 个订单的终点为路口 (x i3 ,y i3 ) 到路口 (x i4 ,y i4 ) 之间的道路中点的右侧。
第二行包含 n − 1 个整数 h 1 , h 2 , ···, h n−1 。
第三行包含 m − 1 个整数 w 1 , w 2 , ···, w m−1 。
接下来 n 行，每行 m 个整数，描述每个路口南北向绿灯的时间，其中的第i 行第 j 列表示 g ij 。
接下来 n 行，每行 m 个整数，描述每个路口东西向绿灯的时间，其中的第i 行第 j 列表示 r ij 。
接下来一行包含四个整数 x 1 , y 1 , x 2 , y 2 ，表示小蓝家的位置在路口 (x 1 ,y 1 )到路口 (x 2 ,y 2 ) 之间的道路中点的右侧。
接下来一行包含一个整数 q，表示订单数量。
接下来 q 行，每行描述一个订单，其中第 i 行包含八个整数 x i1 , y i1 , x i2 , y i2 ,x i3 , y i3 , x i4 , y i4 ，表示第 i 个订单的起点为路口 (x i1 ,y i1 ) 到路口 (x i2 ,y i2 ) 之间的道路中点的右侧，第 i 个订单的终点为路口 (x i3 ,y i3 ) 到路口 (x i4 ,y i4 ) 之间的道路中点的右侧。
输出格式
输出一个实数，表示小蓝完成所有订单最后回到家的最早时刻。四舍五入
保留一位小数。
保留一位小数。
样例输入
2 3 200 100 400 10 20 10 20 40 30 20 20 20 20 20 20 2 1 1 1 1 2 2 1 2 1 2 1 3
样例输出
1620.0
提示
【样例说明】
小蓝有一个订单，他的行车路线如下图所示。其中 H 表示他家的位置，S
表示订单的起点，T 表示订单的终点。小明在最后回家时要在直行的红绿灯路
小蓝有一个订单，他的行车路线如下图所示。其中 H 表示他家的位置，S
表示订单的起点，T 表示订单的终点。小明在最后回家时要在直行的红绿灯路
口等绿灯，等待时间为 20。
