Secrets in Shadows

Long ago, several identical columns (cylinders) stood upright in a large open field. During the day, as the sun moved across the sky, the shadows of the columns swept across the ground. Each column is so tall that its shadow is effectively infinitely long. Everything is viewed from directly above (a top view).

Fig. F-1: The columns (cylinders)

Fig. F-2: Top view of the columns and their shadows

Every column has the same base disk of radius $1$ (diameter $2$), so the shadow cast by a single column is an infinitely long strip whose width equals the diameter, $2$. The width of the whole shadow is the total width of the union of all the individual shadow strips, measured perpendicular to the sun's rays. Because some strips may overlap, this total width changes as the direction of the sun changes.

Fig. F-3: A sun direction that makes the whole shadow narrow

When the whole shadow splits into several disconnected parts, its width is defined as the sum of the widths of those parts.

Fig. F-4: A sun direction that makes the whole shadow wide

The direction of the sun is described by an angle $\theta$. East is $\theta = 0$, south is $\theta = \pi/2$, and west is $\theta = \pi$; the sun rises in the east ($\theta = 0$) and sets in the west ($\theta = \pi$). The $x$-axis points east and the $y$-axis points north, and the center of each column's base disk is given by its $(x, y)$ coordinates.

Fig. F-5: Definition of the sun-direction angle $\theta$

As $\theta$ ranges over $[0, \pi)$, the width of the whole shadow takes different values. Your task is to compute the minimum width $W_{\min}$ and the maximum width $W_{\max}$ of the whole shadow over all sun directions. The field is a flat plane.

The input contains several datasets and ends with a line containing a single 0.

Each dataset has the form:

n
x1 y1
x2 y2
...
xn yn

• $n$ is the number of columns, a positive integer with $1 \le n \le 100$.
• $x_k$ and $y_k$ are the coordinates of the center of the $k$-th column's base disk. They are positive integers with $1 \le x_k, y_k \le 30$, separated by a space.

Each base disk has radius $1$ (diameter $2$). Columns may touch but never overlap, so the distance between any two centers is at least $2$.

For each dataset, print two lines with no extra characters (such as trailing spaces):

• the first line is the minimum width $W_{\min}$ of the whole shadow,
• the second line is the maximum width $W_{\max}$ of the whole shadow.

Print each width rounded to exactly $4$ digits after the decimal point.