nightman - 夜警 (Nightman) Editorial /

Time Limit: 5 sec / Memory Limit: 64 MiB

AtCoder での提出方法

標準入力から入力を読み込み,標準出力へ出力すること.

配点 : 100 点

問題文

広大な敷地の Y センターは,国営の複合研修施設であり,クラブの会合・合宿,市民楽団による定期演奏会,企業の新人研修など,多くの人々にさまざまな目的で利用されている.

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

2008-nightman-grid.png

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

Y センターには b 個の建物がある.建物は全て長方形でその辺は座標軸のいずれかと平行である.建物の位置は 4 個の整数 (s_{i}, t_{i}, u_{i}, v_{i}) (i = 1, ..., b) で表される.i 番目の建物の左下の座標が (s_{i}, t_{i}) であり,右上の座標が (u_{i}, v_{i}) であり,辺上は建物の領域として含まれず,建物と建物が接していても間にはすきまがあり通ることができる.また建物の敷地は重複していない.

夜間の利用者の安全を守るため,a 人の警備員が座標 (x_{1}, y_{1}), ..., (x_{a}, y_{a}) に配置されている.警備員の配置位置は建物の外である.

深夜,Y センター内の警備は以下のように行われる.敷地内のある点で不審物が発見されると,そのたびに全ての警備員に連絡が入る.そして,その点までの移動距離が最も短い警備員が現場に急行し,不審物の確認を行う.警備員は Y センター内を最短距離で移動するが,建物内は深夜はロックされているため,建物の内部を通ることはできない.

(建物の辺は建物に含まれないので,建物の辺に沿って移動することはできる)不審物の確認が済むと,警備員は同じ経路で自分の位置に戻る.次に不審物が発見されたときも同様に警備される.

2008-nightman-example.png

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

ある日の深夜,Y センター内の建物の外で c 個の不審物が発見された.Y センターの大きさと,警備員の位置,建物の位置,そしてある日の深夜に発見された不審物の位置 (p_{1}, q_{1}), ..., (p_{c}, q_{c}) が発見時刻の順に与えられたとき,警備員の移動距離の総和を求めるプログラムを作成せよ.

入力

入力ファイル nightman.in の 1 行目には警備員の数を表す整数 a (1 \leqq a \leqq 10) と建物の数を表す整数 b (1 \leqq b \leqq 50) と不審物の数を表す整数 c (1 \leqq c \leqq 10) が書かれている.

2 行目には Y センターの敷地の大きさを表す 2 つの整数 w, h (1 \leqq w, h \leqq 1000) が横,縦の順に書かれている.

i + 2 行目 (1 \leqq i \leqq a) には,i 人目の警備員の場所を表す 2 つの整数 x_{i}, y_{i} (0 \leqq x_{i} \leqq w,0 \leqq y_{i} \leqq h) が書かれている.j + a + 2 行目 (1 \leqq j \leqq b) には,j 人目の建物の場所を表す 4 つの整数 s_{j}, t_{j}, u_{j}, v_{j} (0 \leqq s_{j} < u_{j} \leqq w,0 \leqq t_{j} < v_{j} \leqq h) が書かれている.k + a + b + 2 行目 (1 \leqq k \leqq c) には,k 人目の不審物の数を表す 2 つの整数 p_{k}, q_{k} (0 \leqq p_{k} \leqq w,0 \leqq q_{k} \leqq h) が書かれている.

出力

出力は標準出力に行う.

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

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

入力例 1

2 4 3
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

出力例 1

30.847

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


Source Name

JOI 2007-2008 春季トレーニング合宿 Contest Day3