题目描述

题目译自 PA 2017 Final Machine learning

Bajtazar 最近对一门科学产生了兴趣，这门科学描述了教计算机自动识别数据中的模式并从中得出结论的方法——即机器学习。在研究这一领域时，他需要考察某个复杂函数 $f$ 的性质。他计算了该函数在多个点 $x_1, x_2, \ldots, x_n$ 上的值，并相应地得到了 $y_1, y_2, \ldots, y_n$。

现在，他希望用一个由两段线性部分组成的连续函数 $g$ 来逼近 $f$；形式上，对于某个 $x \in \mathbb{R}$，$g$ 在自变量小于 $x$ 的区间内是线性的，在自变量大于 $x$ 的区间内也是线性的。

Bajtazar 希望得到一个对 $f$ 的忠实逼近。因此，他希望最小化均方误差：

$$\frac{1}{n} \sum_{i=1}^{n}\left(y_{i}-g\left(x_{i}\right)\right)^{2}$$

输入格式

输入的第一行包含一个整数 $n$ $(1 \le n \le 100000)$。

接下来的 $n$ 行每行包含两个整数 $x_i, y_i$ $(0 \le x_i \le 1000000, 0 \le y_i \le 1000)$。$x_i$ 的值两两不同。

输出格式

输出的第一行且仅一行应包含一个数字，即由上述公式描述的、可达到的最小近似误差。

答案的相对误差或绝对误差不超过 $10^{-6}$ 即可通过。

5
0 1
2 0
1 3
4 4
3 2

0.8333333333333

在第一个样例中，最优的均方误差为 $\frac{5}{6}$。可以通过在左侧设定线性函数 $-\frac{x}{2}+\frac{11}{6}$，并在右侧设定函数 $2x-4$ 来获得该结果。

7
0 0
1 1
2 2
3 4
4 2
5 1
6 0

0.0659340659341

在第二个样例中，最优误差等于 $\frac{6}{91}$。最优函数的图像包含在直线 $\frac{16}{13}x - \frac{2}{13}$ 和 $-\frac{16}{13}x + \frac{94}{13}$ 中。