I have $n$ points that form a grid with empty space and I need to find an algorithm that would calculate the total distance of those points with time complexity lower than $O(n^2)$.a grid with $n=5$ could be represented as a matrix:$$        \begin{matrix}        0 & 0 & 1 \\        1 & 0 & 1 \\        0 & 1 & 1 \\        \end{matrix}$$the distance for point $(1,3)$ is:$1+\sqrt{5}+2+\sqrt{5}=3+2\sqrt{5}$the distance for point $(2,1)$ is:$2+\sqrt{2}+\sqrt{5}$the distance for point $(2,3)$ is:$\sqrt{2}+1$the distance for point $(3,2)$ is:$1$the distance for point $(3,3)$ is:$0$So the total distance is: $7+2\sqrt{2}+3\sqrt{5}$This approach simply calculates separately the distance and then adds it up which doesn't take into account the fact that they are positions in layers. This doesn't look like a super unique issue - is there any existing algorithm for this or does anyone have an idea how to speed this up?EDIT:By Total Distance I mean a situation like this:I pick a point and then calculate the euclidean distance between the picked point and the rest $n-1$ points. Then I choose the next point and I calculate it's distance betwenn it and the rest $n-2$ points, and so on. I then sum up all the distances to get the total.Explanation for distance calculation:The distance for point $(1,3)$ is the sum of euclidean distances between point $(1,3)$ and $(2,1)$, $(2,3)$, $(3, 2)$, $(3,3)$.The distance for point $(2,1)$ is the sum of euclidean distances between point $(2,1)$ and  $(2,3)$, $(3, 2)$, $(3,3)$.and so on...
Total distance between points on a grid
distance measure