No.707 書道
タグ : / 解いたユーザー数 185
作問者 :
ミドリムシ
/ テスター :
nmnmnmnmnmnmnm
問題文
ひみは書道が好きで、暇があれば書道をしている。
今日は縦が$H$マス、横が$W$マスあるいつもより大きな紙を使って書道をしたい。
紙が大きいので紙の外側に立って塗る必要がある。
下の図は「い」を書くときの見本だ。縦$4$マス、横$4$マスの紙を使っている。
下の図において、ひみは赤いマスのいずれかに立って文字を書く。立つことが出来るマスは$(x, y) (0 \leq x \leq H+1$ かつ $0 \leq y \leq W+1$ かつ {$x = 0, x = H+1, y = 0, y = W+1$のうちちょうど一つが成り立つ}$)$
全ての「見本の黒く塗られているマス」について「塗る」という作業をしなければならない。
「塗る」という作業にかかる時間は自分の立っているマスと塗りたいマスの距離 [マス/秒]で計算することが出来る。
ここで、$(x_1, y_1)$と$(x_2, y_2)$の2点間の距離は$\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$で求めることが出来る。
ひみはできるだけ早く書道を終わらせたい。立つことが出来るマスの中で、どこに立てば全ての「見本の黒く塗られているマス」を最速で塗ることが出来るか。
入力
$H$ $W$
$P_{1,1}$ $P_{2,1}$ .. $P_{W,1}$
$P_{1,2}$ $P_{2,2}$ .. $P_{W,2}$
$:$
$P_{1,H}$ $P_{2,H}$ .. $P_{W,H}$
$1 \leq H \leq 50$
$1 \leq W \leq 50$
$P_{i, j} = 0$または$1$
$P_{i, j} = 0$のときは、見本の$(i, j)$のマスが黒く塗られていないことを指し、
$P_{i, j} = 1$のときは、見本の$(i, j)$のマスが黒く塗られていることを指す。
出力
ひみが全ての「見本の黒く塗られているマス」を塗ることが出来るまでにかかる時間 [秒]の最小値を出力せよ。
末尾に改行を入れること。
許容誤差は$10^{-6}$以下。
サンプル
サンプル1
入力
4 4 1001 1001 1001 1100
出力
20.89580466
問題文中の例。
$(0, 3)$に立って書くと、
$(1, 1)$を塗るためにかかる時間は$\sqrt{(0 - 1)^2 + (3 - 1)^2} = 2.236...$
$(1, 2)$を塗るためにかかる時間は$\sqrt{(0 - 1)^2 + (3 - 2)^2} = 1.414...$
$(1, 3)$を塗るためにかかる時間は$\sqrt{(0 - 1)^2 + (3 - 3)^2} = 1$
$(1, 4)$を塗るためにかかる時間は$\sqrt{(0 - 1)^2 + (3 - 4)^2} = 1.414...$
$(2, 4)$を塗るためにかかる時間は$\sqrt{(0 - 2)^2 + (3 - 4)^2} = 2.236...$
$(4, 1)$を塗るためにかかる時間は$\sqrt{(0 - 4)^2 + (3 - 1)^2} = 4.472...$
$(4, 2)$を塗るためにかかる時間は$\sqrt{(0 - 4)^2 + (3 - 2)^2} = 4.123...$
$(4, 3)$を塗るためにかかる時間は$\sqrt{(0 - 4)^2 + (3 - 3)^2} = 4$
合計で$20.895...$秒かかる。
これが最小値（最速）なのでこれを出力する。
サンプル2
入力
5 5 10001 10001 11111 10001 10001
出力
43.26893172
$(0, 3)$に立って書いたときが最も速い。
サンプル3
入力
30 27 101111001101011000001011000 111100011101011110100101010 010001110101011101010100101 000001101000010000110001110 100010011101011111111110110 101100101110001010101011110 001010000010111110011011010 111110011010011100000001110 010101010011001000111001001 100001011100100000100000100 000110011110100111101110010 000000001101010001100010110 111110110110100000010100000 011010001000011100100111001 001011110110010000010001000 000101110001001000110111110 010010110001000100000111100 101101110101101101111100111 100110100011001001111101011 000010010000000000100101011 110001000101101101100000010 011111011101111101011010010 011110011111001110000111110 111111000011000110000010001 110001111011100001110110111 010101000101001011001110101 000101111110110010110000111 111011001101110101101100100 100011000100100011001010100 100010000100110100001111110
出力
6680.72304009
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。