P8424 [JOI Open 2022] Seesaw / Seesaw

**Translated from [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T1. [シーソー](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/seesaw/2022-open-seesaw-statement.pdf) / [Seesaw](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/seesaw/2022-open-seesaw-statement-en.pdf).**

A straight rod of length ${10}^9$ is placed horizontally from left to right. You may ignore the weight of the rod. There are $N$ weights hanging on the rod, each with unit mass. The positions of these $N$ weights are all distinct. The position of the $i$-th weight ($1 \le i \le N$) is $A_i$. That is, the distance from the left end of the rod to the $i$-th weight is $A_i$. At the beginning, we have a box of width $w$. We can place the rod on the box so that the box supports the part of the rod from $l$ to $r$ ($0 \le l < r \le {10}^9$), inclusive of both ends; that is, the interval on the rod from position $l$ to position $r$. Here we must have $r = l + w$. After that, we are not allowed to change the values of $l$ and $r$. Next, we remove the leftmost or the rightmost weight hanging on the rod. We need to repeat this operation $N - 1$ times. During this process, including the initial state and the final state, the center of mass of all weights hanging on the rod must always stay between $l$ and $r$, inclusive. If there are $m$ weights on the rod at positions $b_1, b_2, \ldots, b_m$, then the center of mass is at $\frac{b_1 + b_2 + \cdots + b_m}{m}$. Given $N$ and the positions $A_1, A_2, \ldots, A_N$ of the $N$ weights, write a program to compute the minimum possible width $w$ of the box.

The first line contains a positive integer $N$. The second line contains $N$ non-negative integers $A_1, A_2, \ldots, A_N$.

Output the minimum possible width $w$ of the box. Your program will be judged correct if the absolute error or relative error between your output and the standard answer is at most ${10}^{-9}$.

**[Sample Explanation #1]** The width of the box can be $\frac{5}{6}$. Let $l = \frac{3}{2}, r = \frac{7}{3}$. Do the following operations: - Initially, the center of mass is at $\frac{7}{3}$. - In the first operation, we remove the rightmost weight (the weight at position $4$). The center of mass becomes $\frac{3}{2}$. - In the second operation, we remove the leftmost weight (the weight at position $1$). The center of mass becomes $2$. During this process, the center of mass always stays within the range from $l$ to $r$. Since the width of the box cannot be less than $\frac{5}{6}$, output the decimal form of $\frac{5}{6}$. This sample satisfies the constraints of all subtasks. ---- **[Sample Explanation #2]** This sample satisfies the constraints of all subtasks. ---- **[Constraints]** **This problem uses bundled testdata.** - Subtask 1 (1 point): $N \le 20$. - Subtask 2 (33 points): $N \le 100$. - Subtask 3 (33 points): $N \le 2000$. - Subtask 4 (33 points): no additional constraints. For all testdata, $2 \le N \le 2 \times 10^5$, $0 \le A_1 < A_2 < \cdots < A_N \le {10}^9$. Translated by ChatGPT 5