題目 2595:
藍(lán)橋杯2020年第十一屆國(guó)賽真題-出租車
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 70 解決: 4
題目描述
小藍(lán)在 L 市開出租車。
L 市的規(guī)劃很規(guī)整，所有的路都是正東西向或者正南北向的，道路都可以看成直線段。東西向的道路互相平行，南北向的道路互相平行，任何一條東西向道路垂直于任何一條南北向道路。
從北到南一共有 n 條東西向道路，依次標(biāo)號(hào)為 H 1 , H 2 , ···, H n 。從西到東一共有 m 條南北向的道路，依次標(biāo)號(hào)為 S 1 , S 2 , ···, S m 。每條道路都有足夠長(zhǎng)，每一條東西向道路和每一條南北向道路都相交，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 。道路的每個(gè)路口都有一個(gè)紅綠燈。時(shí)刻 0 的時(shí)候，南北向綠燈亮，東西向紅燈亮，南北向的綠燈會(huì)持續(xù)一段
時(shí)間（每個(gè)路口不同），然后南北向變成紅燈，東西向變成綠燈，持續(xù)一段時(shí)間后，再變成南北向綠燈，東西向紅燈。
已知路口 (i, j) 的南北向綠燈每次持續(xù)的時(shí)間為 g ij ，東西向的綠燈每次持續(xù)的時(shí)間為 r ij ，紅綠燈的變換時(shí)間忽略。
當(dāng)一輛車走到路口時(shí)，如果是綠燈，可以直行、左轉(zhuǎn)或右轉(zhuǎn)。如果是紅燈，可以右轉(zhuǎn)，不能直行或左轉(zhuǎn)。如果到路口的時(shí)候剛好由紅燈變?yōu)榫G燈，則視為
看到綠燈，如果剛好由綠燈變?yōu)榧t燈，則視為看到紅燈。每段道路都是雙向道路，道路中間有隔離欄桿，在道路中間不能掉頭，只能在紅綠燈路口掉頭。掉頭時(shí)不管是紅燈還是綠燈都可以直接掉頭。掉頭的時(shí)間可以忽略。小藍(lán)時(shí)刻 0 從家出發(fā)。今天，他接到了 q 個(gè)預(yù)約的訂單，他打算按照訂單的順序依次完成這些訂單，就回家休息。中途小藍(lán)不準(zhǔn)備再拉其他乘客。
小藍(lán)的家在兩個(gè)路口的中點(diǎn)，小藍(lán)喜歡用 x 1 , y 1 , x 2 , y 2 來(lái)表示自己家的位置，即路口 (x 1 ,y 1 ) 到路口 (x 2 ,y 2 ) 之間的道路中點(diǎn)的右側(cè)，保證兩個(gè)路口相鄰（中間沒(méi)有其他路口）。請(qǐng)注意當(dāng)兩個(gè)路口交換位置時(shí)，表達(dá)的是路的不同兩邊，路中間有欄桿，因此這兩個(gè)位置實(shí)際要走比較遠(yuǎn)才能到達(dá)。小藍(lán)的訂單也是從某兩個(gè)路口間的中點(diǎn)出發(fā)，到某兩個(gè)路口間的中點(diǎn)結(jié)束。小藍(lán)必須按照給定的順序處理訂單，而且一個(gè)時(shí)刻只能處理一個(gè)訂單，不能圖省時(shí)間而同時(shí)接兩位乘客，也不能插隊(duì)完成后面的訂單。小藍(lán)只對(duì) L 市比較熟，因此他只會(huì)在給定的 n 條東西向道路和 m 條南北向道路上行駛，而且不會(huì)駛出 H 1 , H n , S 1 , S m 這幾條道路所確定的矩形區(qū)域（可以到邊界）。小藍(lán)行車速度一直為 1，乘客上下車的時(shí)間忽略不計(jì)。請(qǐng)問(wèn)，小藍(lán)最早什么時(shí)候能完成所有訂單回到家。
L 市的規(guī)劃很規(guī)整，所有的路都是正東西向或者正南北向的，道路都可以看成直線段。東西向的道路互相平行，南北向的道路互相平行，任何一條東西向道路垂直于任何一條南北向道路。
從北到南一共有 n 條東西向道路，依次標(biāo)號(hào)為 H 1 , H 2 , ···, H n 。從西到東一共有 m 條南北向的道路，依次標(biāo)號(hào)為 S 1 , S 2 , ···, S m 。每條道路都有足夠長(zhǎng)，每一條東西向道路和每一條南北向道路都相交，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 。道路的每個(gè)路口都有一個(gè)紅綠燈。時(shí)刻 0 的時(shí)候，南北向綠燈亮，東西向紅燈亮，南北向的綠燈會(huì)持續(xù)一段
時(shí)間（每個(gè)路口不同），然后南北向變成紅燈，東西向變成綠燈，持續(xù)一段時(shí)間后，再變成南北向綠燈，東西向紅燈。
已知路口 (i, j) 的南北向綠燈每次持續(xù)的時(shí)間為 g ij ，東西向的綠燈每次持續(xù)的時(shí)間為 r ij ，紅綠燈的變換時(shí)間忽略。
當(dāng)一輛車走到路口時(shí)，如果是綠燈，可以直行、左轉(zhuǎn)或右轉(zhuǎn)。如果是紅燈，可以右轉(zhuǎn)，不能直行或左轉(zhuǎn)。如果到路口的時(shí)候剛好由紅燈變?yōu)榫G燈，則視為
看到綠燈，如果剛好由綠燈變?yōu)榧t燈，則視為看到紅燈。每段道路都是雙向道路，道路中間有隔離欄桿，在道路中間不能掉頭，只能在紅綠燈路口掉頭。掉頭時(shí)不管是紅燈還是綠燈都可以直接掉頭。掉頭的時(shí)間可以忽略。小藍(lán)時(shí)刻 0 從家出發(fā)。今天，他接到了 q 個(gè)預(yù)約的訂單，他打算按照訂單的順序依次完成這些訂單，就回家休息。中途小藍(lán)不準(zhǔn)備再拉其他乘客。
小藍(lán)的家在兩個(gè)路口的中點(diǎn)，小藍(lán)喜歡用 x 1 , y 1 , x 2 , y 2 來(lái)表示自己家的位置，即路口 (x 1 ,y 1 ) 到路口 (x 2 ,y 2 ) 之間的道路中點(diǎn)的右側(cè)，保證兩個(gè)路口相鄰（中間沒(méi)有其他路口）。請(qǐng)注意當(dāng)兩個(gè)路口交換位置時(shí)，表達(dá)的是路的不同兩邊，路中間有欄桿，因此這兩個(gè)位置實(shí)際要走比較遠(yuǎn)才能到達(dá)。小藍(lán)的訂單也是從某兩個(gè)路口間的中點(diǎn)出發(fā)，到某兩個(gè)路口間的中點(diǎn)結(jié)束。小藍(lán)必須按照給定的順序處理訂單，而且一個(gè)時(shí)刻只能處理一個(gè)訂單，不能圖省時(shí)間而同時(shí)接兩位乘客，也不能插隊(duì)完成后面的訂單。小藍(lán)只對(duì) L 市比較熟，因此他只會(huì)在給定的 n 條東西向道路和 m 條南北向道路上行駛，而且不會(huì)駛出 H 1 , H n , S 1 , S m 這幾條道路所確定的矩形區(qū)域（可以到邊界）。小藍(lán)行車速度一直為 1，乘客上下車的時(shí)間忽略不計(jì)。請(qǐng)問(wèn)，小藍(lán)最早什么時(shí)候能完成所有訂單回到家。
輸入格式
輸入第一行包含兩個(gè)整數(shù) n, m，表示東西向道路的數(shù)量和南北向道路的數(shù)量。
第二行包含 n ? 1 個(gè)整數(shù) h 1 , h 2 , ···, h n?1 。
第三行包含 m ? 1 個(gè)整數(shù) w 1 , w 2 , ···, w m?1 。
接下來(lái) n 行，每行 m 個(gè)整數(shù)，描述每個(gè)路口南北向綠燈的時(shí)間，其中的第i 行第 j 列表示 g ij 。
接下來(lái) n 行，每行 m 個(gè)整數(shù)，描述每個(gè)路口東西向綠燈的時(shí)間，其中的第i 行第 j 列表示 r ij 。
接下來(lái)一行包含四個(gè)整數(shù) x 1 , y 1 , x 2 , y 2 ，表示小藍(lán)家的位置在路口 (x 1 ,y 1 )到路口 (x 2 ,y 2 ) 之間的道路中點(diǎn)的右側(cè)。
接下來(lái)一行包含一個(gè)整數(shù) q，表示訂單數(shù)量。
接下來(lái) q 行，每行描述一個(gè)訂單，其中第 i 行包含八個(gè)整數(shù) x i1 , y i1 , x i2 , y i2 ,x i3 , y i3 , x i4 , y i4 ，表示第 i 個(gè)訂單的起點(diǎn)為路口 (x i1 ,y i1 ) 到路口 (x i2 ,y i2 ) 之間的道路中點(diǎn)的右側(cè)，第 i 個(gè)訂單的終點(diǎn)為路口 (x i3 ,y i3 ) 到路口 (x i4 ,y i4 ) 之間的道路中點(diǎn)的右側(cè)。
第二行包含 n ? 1 個(gè)整數(shù) h 1 , h 2 , ···, h n?1 。
第三行包含 m ? 1 個(gè)整數(shù) w 1 , w 2 , ···, w m?1 。
接下來(lái) n 行，每行 m 個(gè)整數(shù)，描述每個(gè)路口南北向綠燈的時(shí)間，其中的第i 行第 j 列表示 g ij 。
接下來(lái) n 行，每行 m 個(gè)整數(shù)，描述每個(gè)路口東西向綠燈的時(shí)間，其中的第i 行第 j 列表示 r ij 。
接下來(lái)一行包含四個(gè)整數(shù) x 1 , y 1 , x 2 , y 2 ，表示小藍(lán)家的位置在路口 (x 1 ,y 1 )到路口 (x 2 ,y 2 ) 之間的道路中點(diǎn)的右側(cè)。
接下來(lái)一行包含一個(gè)整數(shù) q，表示訂單數(shù)量。
接下來(lái) q 行，每行描述一個(gè)訂單，其中第 i 行包含八個(gè)整數(shù) x i1 , y i1 , x i2 , y i2 ,x i3 , y i3 , x i4 , y i4 ，表示第 i 個(gè)訂單的起點(diǎn)為路口 (x i1 ,y i1 ) 到路口 (x i2 ,y i2 ) 之間的道路中點(diǎn)的右側(cè)，第 i 個(gè)訂單的終點(diǎn)為路口 (x i3 ,y i3 ) 到路口 (x i4 ,y i4 ) 之間的道路中點(diǎn)的右側(cè)。
輸出格式
輸出一個(gè)實(shí)數(shù)，表示小藍(lán)完成所有訂單最后回到家的最早時(shí)刻。四舍五入
保留一位小數(shù)。
保留一位小數(shù)。
樣例輸入
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
提示
【樣例說(shuō)明】
小藍(lán)有一個(gè)訂單，他的行車路線如下圖所示。其中 H 表示他家的位置，S
表示訂單的起點(diǎn)，T 表示訂單的終點(diǎn)。小明在最后回家時(shí)要在直行的紅綠燈路
小藍(lán)有一個(gè)訂單，他的行車路線如下圖所示。其中 H 表示他家的位置，S
表示訂單的起點(diǎn)，T 表示訂單的終點(diǎn)。小明在最后回家時(shí)要在直行的紅綠燈路
口等綠燈，等待時(shí)間為 20。
