There is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that the cost of all groups moving to that point is the minimum. As for how to compute the cost of moving one group to another point, please see the following example.

Group1: (0, 1), 4

Group2: (1, 3), 3

Group3: (2, 0), 5

. 4 . .

. . . 3

5 . . .

If all of these three groups moving to (1, 1), the cost is: 4*((1-0)+(1-1)) + 5*((2-1)+(1-0))+3*((1-1)+(3-1))

### Comments (7) -

Add comment

biuquote

- Comment
- Preview

Use iterator's example for illustration:

{(-100,0,100),(100,0,100),(0,1,1)},(x,y,population)

for x, {(-100,100),(100,100),(0,1)}, 0 is the best.

for y, {(0,100),(0,100),(1,1)}, 0 is the best.

So it's (0, 0)

Is there any better solution for this problem.

cost(x,y) = 5sqrt( (x-2)^2+y^2 ) + 4sqrt( x^2 + (y-1)^2 ) + 3sqrt( (x-1)^2-(y-3)^2 );

then set each partial derivative equal to zero and solve the system (numerically) to get x=0.8793 and y=0.9483.

But If the meeting point is (1,1) the cost will be 20.

To find the (1,1) I just thought I would count how much it costs for every group to move to a location. So I counted that the cost for

(0,*)=13; (1,*)=9; (2,*)=11.

Obviously the first digit should be 1. After the same process for the second digit

(*,0)=13; (*,1)=11; (*,2)=17.

As well, here we see that the second digit should be 1 as well.

After combining them, we get the minimum cost in location (1,1) to be 20.

Split to 2 similar tasks ( horisontal and vertical axises)

For each task:

Create additional array

For each group Put coordinate into array for amount of persons in group times

Find median with quicksort split

This is the answer on current axis

Array preparation takes O(n) times where n - amount of people

Median search - O( log n)

With some modifications it can be reduced to O(amount of groups) and even to O(log n) time (in case of using original data)

But it's 2AM now. )