题目描述

给定平面上的 $n$ 个点 $(x_i,y_i)$, 定义 $d(i,j)=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$, 求 $\sum_{1 \leq i < j \leq n} d(i,j)$.

输入格式

输入的第一行包含一个整数 $n$.

接下来 $n$ 行, 每行两个整数 $x_i,y_i$.

输出格式

输出一行一个实数表示答案, 误差不超过 $10^{-4}$

样例数据

样例输入

3
1 2
-1 3
0 -1

样例输出

9.5214512632858295782294770691381

样例解释

答案即为 $d(1,2)+d(1,3)+d(2,3) = \sqrt{5}+\sqrt{10}+\sqrt{17}$

子任务

对于所有数据, $1 \leq n \leq 5 \times 10^5, -10^6 \leq x_i,y_i \leq 10^6$.

• Subtask 1(10 points): $n \leq 3,000$
• Subtask 2(20 points): $n \leq 40,000$
• Subtask 3(30 points): $n \leq 10^5$
• Subtask 4(20 points): $n \leq 3 \times 10^5$
• Subtask 5(20 points): No additional constraints.