p1042 [noip2003 普及组] 乒乓球

题目描述

在一个长为n的直线上，有m个点，第i个点在直线上的位置为ai，所有点坐标互不相同。我们现在在这条直线上放置一个“弹球”，开始时弹球位于直线上的某一点x0，弹球每次可以向左或向右移动一个单位长度，但不能移动到某个点上。当弹球移动到一个位置x时，它被弹到左边或右边的概率与 |x−ai−1|/(|x−ai−1|+|x−ai|)和 |x−ai|/(|x−ai−1|+|x−ai|) 成正比。设弹球被弹出左边或右边的概率分别为p1,p2，则当p1≠p2时，弹球被弹出的期望位置为 (p1a[i−1]+p2a[i])/2，否则弹球被弹出的位置为pi=a[i−1]+0.5，其中0≤i≤m，a[0]=-∞，a[m]=∞。

现在请你编写程序，计算出让弹球被弹出的期望位置最靠左（即最小）的放置位置x0。

输入格式

第一行包含两个整数n,m，表示直线长度和点数。

第二行包含m个整数，表示所有点的坐标。

输出格式

一个实数，表示期望位置的最小值，精确到小数点后两位。

输入样例

10 5
-2 1 4 7 11

输出样例

1.50

提示

样例解释：当弹球初始位置为1时，它有0.25的概率被弹出左边，0.75的概率被弹出右边。设左边的点为x，右边的点为y，则有：

当弹球被弹出左边时，期望位置为(x+1)/2。
当弹球被弹出右边时，期望位置为(y+1)/2。
综上，当弹球初始位置为1时，期望位置为(4+1)/2=2.5。