No.707 Calligraphy
タグ : / 解いたユーザー数 194
作問者 :
ミドリムシ
/ テスター :
nmnmnmnmnmnmnm
Problem Statement
Himi loves calligraphy and practices it whenever she has free time.
Today she wants to do calligraphy on a paper larger than usual, with $H$ cells vertically and $W$ cells horizontally.
Because the paper is large, she has to stand outside the paper to paint.
The figure below shows the model for writing the character "い". It uses a paper with $4$ cells vertically and $4$ cells horizontally.
In the figure below, Himi stands on one of the red cells to write the character. The cells she can stand on are $(x, y) (0 \leq x \leq H+1$ and $0 \leq y \leq W+1$ and {exactly one of $x = 0, x = H+1, y = 0, y = W+1$ holds}$)$
She must perform the "paint" operation on every "cell painted black in the model".
The time taken by the "paint" operation can be calculated from the distance between the cell she is standing on and the cell she wants to paint [cells/second].
Here, the distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ can be obtained as $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$.
Himi wants to finish her calligraphy as quickly as possible. Among the cells she can stand on, where should she stand to paint all of the "cells painted black in the model" the fastest?
Input
$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$ or $1$
$P_{i, j} = 0$ means that the cell $(i, j)$ of the model is not painted black, and
$P_{i, j} = 1$ means that the cell $(i, j)$ of the model is painted black.
Output
Print the minimum time [seconds] it takes Himi to paint all of the "cells painted black in the model".
Print a newline at the end.
The allowed error is at most $10^{-6}$.
Sample
Sample 1
Input
4 4 1001 1001 1001 1100
Output
20.89580466
This is the example from the problem statement.
If she writes while standing on $(0, 3)$,
the time to paint $(1, 1)$ is $\sqrt{(0 - 1)^2 + (3 - 1)^2} = 2.236...$
the time to paint $(1, 2)$ is $\sqrt{(0 - 1)^2 + (3 - 2)^2} = 1.414...$
the time to paint $(1, 3)$ is $\sqrt{(0 - 1)^2 + (3 - 3)^2} = 1$
the time to paint $(1, 4)$ is $\sqrt{(0 - 1)^2 + (3 - 4)^2} = 1.414...$
the time to paint $(2, 4)$ is $\sqrt{(0 - 2)^2 + (3 - 4)^2} = 2.236...$
the time to paint $(4, 1)$ is $\sqrt{(0 - 4)^2 + (3 - 1)^2} = 4.472...$
the time to paint $(4, 2)$ is $\sqrt{(0 - 4)^2 + (3 - 2)^2} = 4.123...$
the time to paint $(4, 3)$ is $\sqrt{(0 - 4)^2 + (3 - 3)^2} = 4$
The total is $20.895...$ seconds.
This is the minimum (fastest), so print this value.
Sample 2
Input
5 5 10001 10001 11111 10001 10001
Output
43.26893172
Writing while standing on $(0, 3)$ is the fastest.
Sample 3
Input
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
Output
6680.72304009
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。