/
Time Limit: 5 sec / Memory Limit: 64 MiB
AtCoder での提出方法
標準入力から入力を読み込み,標準出力へ出力すること.
配点 : 100 点
問題文
広大な敷地の Y センターは,国営の複合研修施設であり,クラブの会合・合宿,市民楽団による定期演奏会,企業の新人研修など,多くの人々にさまざまな目的で利用されている.
以下の図にように,Y センターの敷地は横 w ×縦 h の長方形である.左下の座標が (0, 0),右上の座標が (w, h) である.
図 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 センター内を最短距離で移動するが,建物内は深夜はロックされているため,建物の内部を通ることはできない.
(建物の辺は建物に含まれないので,建物の辺に沿って移動することはできる)不審物の確認が済むと,警備員は同じ経路で自分の位置に戻る.次に不審物が発見されたときも同様に警備される.
図 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 と出力すればよい.