分数: 6 点
警告
2021 年 4 月 24 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
我们有 N 二维平面中的点;的 i第一点是 (X_i,Y_i)。同一坐标处可以有多个点。 你的任务是选择一个点 P(p, C) 上线 y=C 最小化成本定义如下:
- (成本) = \displaystyle \sum_{i=1}^{N} \bigl((p-X_i)^2+(C-Y_i)^2\bigr)
打印最小成本。
约束
- 输入中的所有值都是整数。
- 1 \le N \le 2 \times 10^5
- |C| \le 10^5
- |X_i|,|Y_i| \le 10^5 (1 \le i \le N)
输入
输入由标准输入按以下格式给出:
N C X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
输出
打印最小成本。 当您的输出与我们的答案的绝对或相对误差最多为 10^{-9}.
示例输入 1
3 2 3 0 3 1 3 3
示例输出 1
6.000000000000000
通过选择 (3,2) as P,我们可以实现最小成本 6.
示例输入 2
2 100000 -100000 100000 -100000 100000
示例输出 2
0.000000000000000
同一位置可以有多个点。
示例输入 3
13 -2 3 -6 -4 7 -8 -8 2 9 1 -3 0 4 -6 6 7 0 1 0 -9 7 6 -1 -7 -2 5 6
示例输出 3
873.769230769230717