10228 - Star not a Tree?

[Shahab]

Any idea to solve such a problem, plz?

I have the idea of derivation of the sum of the distances, but it is really hard and unamusing to code.

Thanks in advance

[Trickster]

Hi everyone,

i

[zac.friggstad]

Hi,

I know this is an old post, but maybe this will still be helpful. Your method is incorrect. Using the centroid will not give the minimum value for the sum of all the distances. (It might be for the sum of the squares of the distances... I would have to think about it more).

How is your multivariate calculus? Think of how you can form a system of 2 equations over two unknowns f(x,y)=0 and g(x,y)=0 where (x,y) represents the location of the hub. Then look up some methods on solving these systems numerically (i.e. not necessarily an exact solution, but close enough for what the problem asks for). The centroid is a good initial approximation for a numerical method, but not the solution. I had my solution accepted on the first try.

Good Luck!

[arsalan_mousavian]

[iggy]

Gradient descent with centroid as a starting point works well too.
Is there a geometrical solution though?