| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 21 | 12 | 11 | 64.706% |
広大な敷地の 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 センター内を最短距離で移動するが,建物 内は深夜はロックされているため,建物の内部を通ることはできない.(建物の辺は建物に含ま れないので,建物の辺に沿って移動することはできる)不審物の確認が済むと,警備員は同じ 経路で自分の位置に戻る.次に不審物が発見されたときも同様に警備される.
図 2: 警備員が現場に急行する図 (○しろまるが警備員,×が不審物)
ある日の深夜,Yセンター内の建物の外で c 個の不審物が発見された.Yセンターの大きさと, 警備員の位置,建物の位置,そしてある日の深夜に発見された不審物の位置 (p1, q1), ... ,(pc, qc) が発見時刻の順に与えられたとき,警備員の移動距離の総和を求めるプログラムを作成せよ.
入力の 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) が書かれている.
出力は標準出力に行う.
警備員の移動距離の総和の小数点以下3桁で出力せよ.誤差は 0.001 以下でなければならない.
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
30.847