Coffee shop problem

[shrewd root]

hey guys i've fought with a problem a few days now...
Given a grid 11*9 where we have five friends A,B,C,D,E on some points, find the best place to put a coffee shop so that the sum of L1 distances each friend has to travel to the shop is minimum

[shrewd root]

we also have to generalize a solution to any grid and any number of friends
the algorithm i proposed is assigning every point on the grid the value of steps every friend needs to get there : https://prnt.sc/l9poFJtDav-y so the point with the lowest value is where we will put the shop
but the teacher said there is a better algorithm with lower complexity
any ideas?

[bitter lodge]

Consider a simpler problem: if the friends are just on a line, what is the best place to put the coffee shop?

This generalises well to 2 dimensions

[unreal wind]

i know the trick for the line but i don;t get how it applies here

well ok i see

i don't see it, you get 14 if you pick (1,1) but the optimal is (2,2) with 12

no (3,3) with 10 of course

@bitter lodgewhat's the trick

[unreal wind]

oh

i get it, there's 5 points, not 3 for each coordinate

sorry×4

[rapid viper]

is it manhattan distance or euclidean distance

ig manhattan?

[unreal wind]

yes

L1 means manhattan

[rapid viper]

oh didnt realize that mb

[mortal wasp]

.close