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



可复制的 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