[COCI2011-2012#5] BLOKOVI
题目描述
平面直角坐标系种有 $N$ 个质量为 $m_{i}$ ,长为 $2$,高为 $h$ 的矩形,使得:
* 矩形的边缘与坐标轴平行;
* 矩形的下层与 $y$坐标不重合,且为以下值:$0,h,2h,3h,\dots,(N-1)h$;
* 最低的矩形左下角的坐标为 $(-2,0)$,右下角与原点重合。
![](https://cdn.luogu.com.cn/upload/image_hosting/rjzp667k.png)
定义一个矩阵的 X 中心是其下边的中点的 X 坐标。一个或多个矩形的 X 中心是其 X 中心的加权平均值。它的计算方法为:
$$
Xbarycetre=\frac{\sum_{i}m_{i}\times Xcentre(i)}{\sum_{i}m_{i}}
$$
其中 `Xbarycetre` 表示一个或多个矩形的 X 中心,`Xcentre` 表示一个矩阵的 X 中心。
换句话说,其值为每个矩形的质量乘以它的 X 中心之积除以矩形的总质量。
对于每一个矩形,如果它**上面的矩形**的 X 中心与其的 X 中心的距离小于等于 $1$,则称这些矩形组成的排列是稳定的。
例如,左图的排列是不稳定的,因为上面两个矩形的 X 中心到下面的矩形的X中心的距离大于 $1$。而右图的排列是稳定的。
给出所有矩形的质量,求其可以组成的稳定排列中的矩形的最大 X 坐标。
你不能改变矩形的顺序,它们从**基本**低到高给出。
输入输出格式
输入格式
第一行,一个整数 $N$,表示矩形的数量。
接着 $N$ 行,每行一个整数 $m_{i}$,表示第 $i$ 个矩形的质量。
输出格式
一行,一个小数,表示答案,答案在 $0.000001$ 的误差内均为正确。
输入输出样例
输入样例 #1
2
1
1
输出样例 #1
1.00000000
输入样例 #2
3
1
1
1
输出样例 #2
1.50000000
输入样例 #3
3
1
1
9
输出样例 #3
1.90000000
说明
有 $30\%$ 的数据,矩形的质量从大到小给出。
$2\le N\le 3\times 10^{5}$,$1\le m_{i}\le 10^{4}$。
题目译自 [COCI 2011/2012 #5 T5](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。