发布时间: 2016年12月3日 16:34 最后更新: 2016年12月3日 16:34 时间限制: 1000ms 内存限制: 65536M

Random walks are used to model a wide range of phenomena, from Brownian motion to gambling. Forexample, a gambler who bets on heads or tails on a coin toss wins or loses his bet each turn. The amount ofmoney the gambler has throughout the game is a random walk. Although the bets in each turn may bedifferent, it is easy to see that the gambler wins the maximum amount of money if he wins every turn.Similarly, he loses the maximum amount if he loses every turn.We consider the following two−dimensional variation of the random walk. We are given n two−dimensionalnonzero vectors vi = (xi, yi), no two of which are parallel. In step i, a coin is flipped. If it is heads, we move ximeters in the x direction and yi meters in the y direction. If it is tails, we move −xi and −yi meters in the x andy directions.We are interested in computing the maximum distance we can be away from our starting point. This is easy inone−dimension, but it is not so easy in the two−dimensional version.

The input consists of a number of test cases. Each test case starts with a line containing the integer n, which is

at most 100. Each of the next n lines gives a pair of integers xi and yi specifying vi. The coordinates are less

than 1000 in magnitude. The end of input is specified by n = 0.

For each test case, print on a line the maximum distance we can be away from the starting point, in the format

shown below. Output the answer to 3 decimal places.

复制

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

Maximum distance = 3.000 meters. Maximum distance = 5.099 meters. Maximum distance = 37.336 meters.