This page is still under construction.

Parts of this page are still being built. What you see may change.

Random Walk

Time limit1sMemory limit128 MB

Summary
Given n nonparallel 2D vectors, choose a sign for each so the resulting sum has maximum Euclidean length.
Level

Medium7 of 10

Topics
Geometry, Greedy, Sorting, Math
Solved
No attempts yet

Problem

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 nn nonzero two-dimensional vectors vi=(xi,yi)v_i = (x_i, y_i), no two of which are parallel. In step ii a coin is flipped: on heads you move xix_i meters in the xx direction and yiy_i meters in the yy direction; on tails you move −xi-x_i and −yi-y_i meters instead. After all nn steps the displacement from the origin is ∑i=1nεivi\sum_{i=1}^{n} \varepsilon_i v_i, where each εi∈{+1,−1}\varepsilon_i \in \{+1, -1\}.

Compute the maximum possible distance from the starting point, that is max⁡ε∈{−1,+1}n∥∑i=1nεivi∥\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.

Input

The input consists of several test cases. Each test case begins with a line containing the integer nn (1≤n≤1001 \le n \le 100). Each of the next nn lines contains two integers xix_i and yiy_i describing viv_i; each coordinate is less than 10001000 in magnitude. A line containing n=0n = 0 marks the end of the input and is not processed.

Output

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.

Examples4

  1. Example 1

    Input
    3
1 1
0 1
-1 1
2
4 0
1 1
7
1 3
-2 -7
7 8
-2 9
-7 -3
4 -3
-2 -2
0
    Expected output
    Maximum distance = 3.000 meters.
Maximum distance = 5.099 meters.
Maximum distance = 37.336 meters.

  2. Example 2

    Input
    1
3 4
0
    Expected output
    Maximum distance = 5.000 meters.

  3. Example 3

    Input
    2
1 0
0 1
0
    Expected output
    Maximum distance = 1.414 meters.

  4. Example 4

    Input
    1
0 1
2
3 0
0 4
0
    Expected output
    Maximum distance = 1.000 meters.
Maximum distance = 5.000 meters.