Wrapping Trees

After last year’s spectacular failure, the Alberta Christmas Paraphernalia Company (ACPC) is getting an early start on their Christmas tree business this year. With all the extra time they have to prepare, the plan is to use some algorithmic methods to optimize their profits.

The ACPC would like to wrap a single piece of string around
each tree so that they can tightly pack them into the
warehouse. The tree supplier has kindly sent you a
specification of the shapes of the trees. The cross section of
the tree that you want to wrap the string around can be
represented in compressed form by an $n$ by $n$ binary image, where each pixel
corresponds to a $1$ cm by
$1$ cm region of the tree.
Unfortunately, as trees are very complicated shapes, it would
take an infinite amount of time for you to download the
complete uncompressed image of a tree. Luckily, the trees are
of premium quality and thus have a very nice recursive
structure. The full uncompressed image of the tree can be
computed by recursively replacing every `1` pixel in the compressed image with a scaled
down copy of the entire image *an infinite number of
times*. Note that the dimensions of the full uncompressed
image are still $n$ cm by
$n$ cm, the same as the
compressed image.

Given a compressed specification of a tree, your task is to
find the shortest possible length of string (in centimeters)
that can wrap completely around the perimeter of all `1` pixels in the corresponding uncompressed
tree.

The first line of input will contain an integer $n$ denoting the both the height and
width of the compressed image in centimeters. You may assume
that $1\le n\le 10^3$. The
following $n$ lines will
contain $n$ characters.
Each character will be either a `0` or
`1` describing the pixels of the
compressed image.

Output the smallest possible length of string that can completely enclose all points in the uncompressed tree corresponding to the given compressed tree. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-5}$.

Sample Input 1 | Sample Output 1 |
---|---|

1 1 |
4 |

Sample Input 2 | Sample Output 2 |
---|---|

3 000 111 000 |
6 |

Sample Input 3 | Sample Output 3 |
---|---|

5 10100 00101 00111 01100 00111 |
17.2656990001 |