랜덤 워크

랜덤 워크(random walk)는 브라운 운동부터 도박까지 다양한 현상을 모형화하는 데 쓰인다. 예를 들어 동전을 던져 앞면 또는 뒷면에 돈을 거는 도박꾼은 매 턴마다 건 돈을 따거나 잃으며, 시간이 지남에 따라 도박꾼이 가진 돈의 양은 하나의 랜덤 워크가 된다. 매 턴 거는 금액이 다르더라도, 모든 턴을 이기면 가장 많은 돈을, 모든 턴을 지면 가장 적은 돈을 갖게 됨은 쉽게 알 수 있다.

여기서는 다음과 같은 2차원 변형을 생각한다. 서로 평행하지 않은, 0이 아닌 2차원 벡터 $n$개 $v_i = (x_i, y_i)$가 주어진다. $i$번째 단계에서 동전을 던져, 앞면이면 $x$ 방향으로 $x_i$만큼, $y$ 방향으로 $y_i$만큼 이동하고, 뒷면이면 대신 $-x_i$, $-y_i$만큼 이동한다. $n$개의 단계를 모두 마치면, 각 $\varepsilon_i \in {+1, -1}$에 대해 출발점으로부터의 변위는 $\sum_{i=1}^{n} \varepsilon_i v_i$가 된다.

출발점에서 도달할 수 있는 최대 거리, 즉 $\max_{\varepsilon \in {-1,+1}^n} \left\lVert \sum_{i=1}^{n} \varepsilon_i v_i \right\rVert$을 구하라. 1차원에서는 쉽지만 2차원에서는 그리 간단하지 않다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 $n$ ($1 \le n \le 100$)이 주어진다. 이어지는 $n$개의 줄에는 각각 $v_i$를 나타내는 두 정수 $x_i$와 $y_i$가 주어지며, 각 좌표의 절댓값은 $1000$보다 작다. $n = 0$인 줄은 입력의 끝을 나타내며 처리하지 않는다.

각 테스트 케이스마다 다음 형식에 정확히 맞추어 한 줄을 출력한다.

Maximum distance = D.DDD meters.

여기서 D.DDD는 출발점으로부터의 최대 거리를 소수점 아래 셋째 자리까지 반올림한 값이다.