Developing.ru

Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна.

А здесь то чего сложного? Двойной цикл и ни каких гвоздёв.

Не такая уж и простая задача на самом деле. Ну если же Вы знаете ответ, то напишите, пожалуйста.

Кстати! Пишут, что только для 3 точек можно найти центр. Я, как профессионал, думаю, что это правда.

Для 4 точек уже центр не находится. Верно товарищи?

Слива писал(а):Для 4 точек уже центр не находится. Верно товарищи?

Нет. На окружности можно отметить произвольное количество точек и ото всех них до центра будет минимальное расстояние

Ну это когда строго окружность, я имел ввиду для случайных точек, используйте функцию rand() в своих умозаключениях.
http://baumanki.net/show-document/1-591 ... a3031dd/2/ - Рис. 7. Из этого рисунка и из других статей следует, что центр треуготльника лежит на пересечении серединных перпендикуляров.

Слива писал(а):используйте функцию rand() в своих умозаключениях.

А вы в таком случае используйте условие задачи Нет задачи найти центр для четырёх и более произвольных точек. Есть задача найти из N точек максимально близкую от центра.

Есть один вариант решения. Не знаю подойдет или нет, но в общем смысл в следующем. Находятся MinX, MaxX, MinY, MaxY - коробка или границы в которой лежат все точки. Это прямоугольник. Потом находится центр этого прямоугольника. Это и будет искомая точка. Верно?

Слива писал(а):Это и будет искомая точка. Верно?

Нет. См. условие задачи - надо из массива в N точек выбрать одну, а не построить ещё одну N+1ю точку.

Это во-первых. А во-вторых, задача не имеет геометрического решения. Чем больше точек будет в одной из половин "коробки" тем дальше искомая точка будет находится от геометрического центра.

Ну и в-третьих, поиск минимума и максимума - это дополнительный обход массива.