Random Walk

Random walks model many phenomena, from Brownian motion to gambling. For example, a gambler who bets on heads or tails on each coin toss wins or loses the bet every turn, and the amount of money the gambler holds over time is a random walk. Although the bet may differ each turn, it is easy to see that the gambler ends with the most money by winning every turn, and with the least money by losing every turn.

We study the following two-dimensional variant. You are given $n$ nonzero two-dimensional vectors $v_i = (x_i, y_i)$, no two of which are parallel. In step $i$ a coin is flipped: on heads you move $x_i$ meters in the $x$ direction and $y_i$ meters in the $y$ direction; on tails you move $-x_i$ and $-y_i$ meters instead. After all $n$ steps the displacement from the origin is $\sum_{i=1}^{n} \varepsilon_i v_i$, where each $\varepsilon_i \in {+1, -1}$.

Compute the maximum possible distance from the starting point, that is $\max_{\varepsilon \in {-1,+1}^n} \left\lVert \sum_{i=1}^{n} \varepsilon_i v_i \right\rVert$. This is easy in one dimension, but not so easy in two.

The input consists of several test cases. Each test case begins with a line containing the integer $n$ ($1 \le n \le 100$). Each of the next $n$ lines contains two integers $x_i$ and $y_i$ describing $v_i$; each coordinate is less than $1000$ in magnitude. A line containing $n = 0$ marks the end of the input and is not processed.

For each test case, print one line in exactly this format:

Maximum distance = D.DDD meters.

where D.DDD is the maximum distance from the starting point, rounded to exactly three decimal places.