No.707 書道

問題提出提出一覧質問統計解説

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が

10^{- 6}

以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 190
作問者 :

ミドリムシ / テスター :

nmnmnmnmnmnmnm

2 ProblemId : 1960 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2018-06-29 22:37:49

問題文

ひみは書道が好きで、暇があれば書道をしている。
今日は縦が $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

入力

出力

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

入力

出力

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もしくは右上の雲マークをクリックしてアカウントを作成してください。