P26923 [AtCoder] Points and Costs
NOI
题目描述

Problem Description

There are $ N $ points on a two-dimensional plane. The $ i $ -th point is located at $ (X_i, Y_i) $. Multiple points may exist at the same coordinates. Your task is to choose a point $ P(p, C) $ on the line $ y = C $ to minimize the cost defined below:

  • (Cost) $= \displaystyle\sum_{i=1}^{N} \bigl((p - X_i)^2 + (C - Y_i)^2\bigr)$

Output the minimum possible cost.

Input Format

The input is given from the standard input in the following format:

$ N $ $ C $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $\vdots$ $ X_N $ $ Y_N $

Output Format

Output the minimum possible cost. The answer will be considered correct if the absolute or relative error is within $ 10^{-9} $.

Sample Input and Output

Sample Input #1

3 2
3 0
3 1
3 3

Sample Output #1

6.000000000000000

Sample Input #2

2 100000
-100000 100000
-100000 100000

Sample Output #2

0.000000000000000

Sample Input #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

Sample Output #3

873.769230769230717

Notes/Hints

Constraints

  • All input values are integers.
  • $1 \le N \le 2 \times 10^5$
  • $|C| \le 10^5$
  • $|X_i|, |Y_i| \le 10^5$ $(1 \le i \le N)$

Sample Explanation 1

By choosing $ P $ at $ (3, 2) $, the cost is minimized to $ 6 $.

Sample Explanation 2

Multiple points can exist at the same position.

输入格式

见题面 Input 部分

输出格式

见题面 Output 部分

样例输入
3 2 3 0 3 1 3 3
样例输出
6.000000000000000