Problem Description
The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.
There are n palaces in the underworld, which can be located on a 2-Dimension plane with (x,y) coordinates (where x,y are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.
However, the underworld is mysterious and changes all the time. At different times, exactly one of the n palaces disappears.
Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.
Print the sum of the distance after every single palace has disappeared.
To avoid floating point error, define the distance d between palace (x1,y1) and (x2,y2) as d=(x1−x2)2+(y1−y2)2.
Input
The first line of the input contains an integer T (1≤T≤5), which denotes the number of testcases.
For each testcase, the first line contains an integers n (3≤n≤105), which denotes the number of temples in this testcase.
The following n lines contains n pairs of integers, the i-th pair (x,y) (−105≤x,y≤105) denotes the position of the i-th palace.
Output
For each testcase, print an integer which denotes the sum of the distance after every single palace has disappeared.
Sample Input
1
3
0 0
1 1
2 2
Sample Output
12
https://blog.csdn.net/liangzhaoyang1/article/details/51954274
简单来看，似乎是n个每次都只去除一个，计算剩下的距离，也就是算完后复原，去除另外一个，继续。
因此只需要一个二维距离矩阵，计算出距离，注意坐标计算不用开方，直接用。
显然是一个对称矩阵，每去除一个点，就是对角线上的一个点的十字线上的值清除，n次以后，全图清除两次，所以为（n-2）*全距离和，而全距离和等于矩阵和/2‘。
实际上，算距离和 不需要矩阵，一个n数组就行了，二重循环，i=0，j=i，向后累积距离即可。
但是如果是每次要计算去掉后继续去掉这种情况，不断累加，那就比较复杂因为共n！种排列方法，考虑到排法平均性，也可以用类似的方法找答案。
因为每两个点距离在排列中幸存的次数是均一的，而幸存的计算是：第一次没选两个点，n-2，下一次又没有选，n-1-2，下一次n-2-2。。。。。这个计算很复杂，也就是2（n-2)+2（n-2)*(n-3)++++++，排列组合二项式公式，Am（n-2)·的和｛（n-2)!/m！，m从1到n-3，可以一个循环搞定｝。