I’m wondering if a centroid based solution should work for this problem.
It seems that the shortest distance to travel for N people to meet will be a centroid based on their coordinates.
So the centroid coordinates will be:
cx = (x1 + x2 + … + xN) / N
cy = (y1 + y2 + … + yN) / N
And then (because of a rounding error) one would just need to examine the rectangle of size 9 (points around centroid) to check the sums of distance from each of the 9 points to each person coordinate.
If this is a correct approach it will reduce the time complexity to O(n + 9*n) which is O(n)
Type your question above this line.
Course: https://www.educative.io/collection/5642554087309312/5679846214598656
Lesson: https://www.educative.io/collection/page/5642554087309312/5679846214598656/120001