Closest Meeting Point

Statement

There is an MxM grid where N people live. These N people want to meet such that the total travel distance is minimized. The travel distance is to be calculated using the Euclidean distance metric. For two points on this grid, (x​1,y​1) and (x​2, y2), the Euclidean distance between them is given by:

$$d=\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

We use Euclidean distance here because the people on the grid can move diagonally as well.

Note: We cannot use Manhattan distance ($d = |x_2-x_1| + |y_2-y_1|$) here because it is a measure of the horizontal and vertical distance and does not cover the diagonal distance.

Example

Consider a 5x5 grid with 3 people, located at:

A (1, 2), B (3, 3), and C (4, 2).