我有$n$形成带有空白空间的网格的点，我需要找到一种算法来计算这些点的总距离，时间复杂度低于$O(n^2)$.

一个网格$n=5$可以表示为一个矩阵：

点的距离$(1,3)$是： $1+\sqrt{5}+2+\sqrt{5}=3+2\sqrt{5}$

点的距离$(2,1)$是： $2+\sqrt{2}+\sqrt{5}$

点的距离$(2,3)$是： $\sqrt{2}+1$

点的距离$(3,2)$是： $1$

点的距离$(3,3)$是： $0$

所以总距离为：$7+2\sqrt{2}+3\sqrt{5}$

这种方法只是单独计算距离，然后将其相加，这并没有考虑到它们是层中的位置这一事实。

这看起来不像是一个超级独特的问题 - 是否有任何现有的算法或者有没有人知道如何加快这个速度？

编辑：总距离是指这样的情况：我选择一个点，然后计算所选择的点与其余点之间的欧几里得距离$n-1$点。然后我选择下一个点并计算它与其余点之间的距离$n-2$积分等等。然后我总结所有距离以获得总数。

距离计算说明：点的距离$(1,3)$是点之间的欧几里得距离之和$(1,3)$和$(2,1)$,$(2,3)$,$(3, 2)$,$(3,3)$. 点的距离$(2,1)$是点之间的欧几里得距离之和$(2,1)$和 $(2,3)$,$(3, 2)$,$(3,3)$. 等等...