#P2714. Random Walk
Random Walk
问题描述
随机游走被广泛用于模拟各种现象,从布朗运动到赌博行为。例如,一个赌徒在每次抛硬币时赌正面或反面,每轮都会赢或输掉赌注。赌徒在整个游戏过程中的资金变化就是一个随机游走过程。虽然每轮的赌注可能不同,但很容易看出:如果赌徒每轮都赢,他将获得最大金额;反之如果每轮都输,他将损失最大金额。
现在我们考虑以下二维随机游走的变体:给定个二维非零向量,且任意两个向量都不平行。在第步,我们抛硬币决定移动方向:如果是正面,则在方向移动米,方向移动米,如果是反面,则在方向移动米,方向移动米。
我们需要计算从起点出发可能达到的最大距离。一维情况下这个问题很简单,但在二维情况下则较为复杂。
输入格式
输入包含多个测试用例: 每个测试用例以整数开始() 接下来行,每行给出两个整数和,表示向量 所有坐标值的绝对值小于 输入以结束。
输出格式
对于每个测试用例,输出一行表示最大距离,格式如下:要求输出结果保留位小数。
输入样例
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年洛基山脉地区编程竞赛