当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6776：Distance

题目描述
小沃沃所在的世界是一个二维平面。他有 $n$ 个朋友，第 $i$ 个朋友距离他的距离为 $a[i]$，小沃沃并不知道这些朋友具体在什么点上。

请问在最优情况下，小沃沃的朋友两两之间的欧几里得距离的和的最小值是几？

假设小沃沃的位置为 $P_0 = (x_0,y_0)$，第 $i$ 个朋友的位置为 $P_i = (x_i,y_i)$，对于所有的 $i$，需要满足 $dist(P_0, P_i) = a[i]$，并且$\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{dist(P_i,P_j)}}$ 最小，其中 $dist(X,Y)$ 为连接点 $X$ 和点 $Y$ 的线段的长度。$x_i,y_i$ 都可以是任意实数。
输入解释
第一行一个正整数 $test(1 \leq test \leq 10)$ 表示数据组数。

对于每组数据，第一行一个正整数 $n(1 \leq n \leq 100000)$。

接下来一行 $n$ 个整数，第 $i$ 个整数 $a[i](1 \leq a[i] \leq 1000000000)$ 表示第 $i$ 个朋友和小沃沃的距离。
输出解释
对每组数据输出一行一个数，表示 $\sum_{i=1}^{n-1}{\sum_{j=i+1}^{n}{dist(P_i,P_j)}}$ 的最小值。答案需要四舍五入到整数。
输入样例 
2
2
3 5
5
1 2 3 4 5
输出样例 
2
20
来自杭电HDUOJ的附加信息
Recommend heyang
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2020 年百度之星·程序设计大赛 - 初赛二
源链接： HDU-6776
最后修改于 2020-10-25T23:34:17+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 65536/65536K(Java/Others)