#P2714. Random Walk

Random Walk

问题描述

随机游走被广泛用于模拟各种现象,从布朗运动到赌博行为。例如,一个赌徒在每次抛硬币时赌正面或反面,每轮都会赢或输掉赌注。赌徒在整个游戏过程中的资金变化就是一个随机游走过程。虽然每轮的赌注可能不同,但很容易看出:如果赌徒每轮都赢,他将获得最大金额;反之如果每轮都输,他将损失最大金额。

现在我们考虑以下二维随机游走的变体:给定nn个二维非零向量vi=(xi,yi)v_i = (x_i, y_i),且任意两个向量都不平行。在第ii步,我们抛硬币决定移动方向:如果是正面,则在xx方向移动xix_i米,yy方向移动yiy_i米,如果是反面,则在xx方向移动xi-x_i米,yy方向移动yi-y_i米。

我们需要计算从起点出发可能达到的最大距离。一维情况下这个问题很简单,但在二维情况下则较为复杂。

输入格式

输入包含多个测试用例: 每个测试用例以整数nn开始(n100n \leq 100) 接下来nn行,每行给出两个整数xix_iyiy_i,表示向量viv_i 所有坐标值的绝对值小于10001000 输入以n=0n=0结束。

输出格式

对于每个测试用例,输出一行表示最大距离,格式如下:Maximumdistance=X.XXXmeters.Maximum distance = X.XXX meters.要求输出结果保留33位小数。

输入样例

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.

题目来源

2005年洛基山脉地区编程竞赛