Minimize Total Manhattan Distance to a Meeting Point

Problem Given points on a grid with a population at each point, choose a meeting point that minimises the total Manhattan travel cost for everyone. Moving one person from (x, y) to target (a, b) costs |x-a| + |y-b|. Return the minimum achievable total cost.

Input / Output

• Input: points, an array of [x, y] pairs; people, where people[i] is the number of persons standing at points[i].
• Output: an integer — the minimum total cost summed over every person.

Constraints

• Number of points < 10^5, so an O(n^2) all-pairs evaluation is too slow.
• Coordinates and populations may be large — the total cost can overflow 32 bits, so accumulate in 64-bit.
• The meeting point need not be one of the input points.

Example

• points = [[0,0],[2,0]], people = [1,3] → the weighted median in x is 2 (3 of the 4 people already stand at x=2); cost = 30 + 12 = 2. The unweighted midpoint x=1 would cost 4 — the weights, not the point count, drive the answer.