Тема: Место встречи (изменить нельзя)
Доброго времени суток!
Пожалуйста помогите найти какой алгоритм решает следующую задачу.
Даны N точек(координат) в виде (-1;0) (20;5) ... (3;2)
Задача - найти такую точку, сумма расстояний от которой до всех остальных будет минимальной.
В задаче также указывается что происходит движение по массиву где переход в каждую соседнюю ячейку (в том числе по диагонали) имеет длину 1. Как бы по аналоги с шахматным королем, но мне кажется здесь это не принципиально, хотя может я не прав.
Подходит ли для этой задачи алгоритм Алгоритм Форда-Беллмана? Или что-то другое? Буду очень признателен.
Пример: Даны точки (0;1) (2;5) (3;1) (4;0)
Суммы путешействий будут 11, 13, 8 и 10. Минимальной из них это 8. Ответ: 8.