J - Points to Cost Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

二次元平面上に点が N 個あります。このうち i 個目の点は (X_i,Y_i) です。同じ座標に点が複数あることもあります。 あなたへの課題は、直線 y=C 上から一点 P(p,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

P を (3,2) にとることにより、コストは最小の 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

Score : 6 points

Warning

Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

We have N points in a two-dimensional plane; the i-th point is (X_i,Y_i). There can be multiple points at the same coordinates. Your task is to choose a point P(p, C) on the line y=C to minimize the cost defined as follows:

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

Print the minimized cost.

Constraints

  • All values in input 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)

Input

Input is given from Standard Input in the following format:

N C
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the minimized cost. Your output is considered correct when its absolute or relative error from our answer is at most 10^{-9}.

Sample Input 1

3 2
3 0
3 1
3 3

Sample Output 1

6.000000000000000

By choosing (3,2) as P, we can achieve the minimum cost of 6.

Sample Input 2

2 100000
-100000 100000
-100000 100000

Sample Output 2

0.000000000000000

There can be multiple points at the same position.

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