← 返回题目列表

AtCoder · joisc2008_nightman

nightman. 夜行者

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

夜警 (Nightman) - 原题 PDF 第 1 页
原题PDF第4页
夜警 (Nightman) - 原题 PDF 第 2 页
原题PDF第5页
夜警 (Nightman) - 原题 PDF 第 3 页
原题PDF第6页
可复制的 PDF 提取文本
Nightman: 夜警


input ファイル“nightman.in”
output 標準出力
ソースファイルnightman.c/nightman.cpp
時間制限5 秒/ データ


 広大な敷地のY センターは,国営の複合研修施設であり,クラブの会合・合宿,市民楽団に

よる定期演奏会,企業の新人研修など,多くの人々にさまざまな目的で利用されている.

 以下の図にように,Y センターの敷地は横w ×縦h の長方形である.左下の座標が(0, 0),右

上の座標が(w, h) である.





              図1: 横8,縦6 のY センター(w = 8, h = 6 の場合)



 Y センターにはb 個の建物がある.建物は全て長方形でその辺は座標軸のいずれかと平行で

ある.建物の位置は4 個の整数(si, ti, ui, vi) (i = 1, ..., b) で表される.i 番目の建物の左下の座

標が(si, ti) であり,右上の座標が(ui, vi) であり,辺上は建物の領域として含まれず,建物と建

物が接していても間にはすきまがあり通ることができる.また建物の敷地は重複していない.

 夜間の利用者の安全を守るため,a 人の警備員が座標(x1, y1), ... ,(xa, ya) に配置されている.

警備員の配置位置は建物の外である.

 深夜,Y センター内の警備は以下のように行われる.敷地内のある点で不審物が発見される

と,そのたびに全ての警備員に連絡が入る.そして,その点までの移動距離が最も短い警備員

が現場に急行し,不審物の確認を行う.警備員はY センター内を最短距離で移動するが,建物

内は深夜はロックされているため,建物の内部を通ることはできない.(建物の辺は建物に含ま

れないので,建物の辺に沿って移動することはできる)不審物の確認が済むと,警備員は同じ

経路で自分の位置に戻る.次に不審物が発見されたときも同様に警備される.



                            夜警–1/3

!   !
                    !





                "      "


            図2: 警備員が現場に急行する図(○が警備員,×が不審物)



 ある日の深夜,Y センター内の建物の外でc 個の不審物が発見された.Y センターの大きさと,

警備員の位置,建物の位置,そしてある日の深夜に発見された不審物の位置(p1, q1), ... ,(pc, qc)

が発見時刻の順に与えられたとき,警備員の移動距離の総和を求めるプログラムを作成せよ.


Input. 入力ファイルnightman.in の1 行目には警備員の数を表す整数a  (1 ≦a ≦10) と建

物の数を表す整数b (1 ≦b ≦50) と不審物の数を表す整数c (1 ≦c ≦10) が書かれている.

  2 行目にはY センターの敷地の大きさを表す2 つの整数w, h  (1 ≦w, h ≦1000) が横,縦の

順に書かれている.

   i + 2 行目(1 ≦i ≦a) には,i 人目の警備員の場所を表す2 つの整数xi, yi (0 ≦xi ≦w, 0 ≦

yi ≦h) が書かれている.j + a + 2 行目(1 ≦j ≦b) には,j 人目の建物の場所を表す4 つの整数

sj, tj, uj, vj (0 ≦sj < uj ≦w, 0 ≦tj < vj ≦h) が書かれている.k + a + b + 2 行目(1 ≦k ≦c)

には,k 人目の不審物の数を表す2 つの整数pk, qk (0 ≦pa ≦w, 0 ≦qa ≦h) が書かれている.


Output. 出力は標準出力に行う.

 警備員の移動距離の総和の小数点以下3 桁で出力せよ.誤差は0.001 以下でなければならない.





                            夜警–2/3

例

次の例は図2 の場合である.

 nightman.in 標準出力
 2 4 3        30.847
 8 6
 3 0
 8 0
 2 1 3 3
 3 2 5 4
 5 1 6 2
 6 4 7 5
 4 5
 6 4
 1 5

 この場合,最短距離は30.8473 · · · なので, 30.847 か30.848 と出力すればよい.





                            夜警–3/3