Здравствуйте, Уважаемые программисты! Я открыла для себя удивительный язык С++ совсем недавно. Да некоторых пор проблем не возникало (язык легко дается). Но вот задали задачку, к которой я не знаю, с какой стороны подобраться... Звучит она так: Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна! Единственное, что я точно знаю, без многомерных массивов здесь не обойтись. Очень надеюсь на вашу помощь в решении этого вопроса! Заранее благодарна!

Можно и без многомерных, обычного вектора (который std::vector) хватит.

В принципе, действительно нет необходимости в многомерном массиве... Достаточно 2 одномерных:
1. массив координат точек (на N элементов)
2. массив сумм расстояний для каждой точки (на N элементов)
Что делать - идешь по первому массиву и считаешь сумму расстояний для i-ой точки и записываешь в i-ый элемент второго массива. Затем находишь во втором массиве минимальный элемент - его индекс позволит узнать точку, которой он соответствует.

А, мы такое делали.. Ток не вышло ничего)

Это сообщение отредактировал(а) Garcian - 10.12.2008, 20:11

Впринципе понятно... Только с геометрией не все хорошо,   

случай клинический...
есть множество точек {(x,y)}
искомая точка это (Xсредн,Yсредн)

какие многомерные массивы... какие std::vector.... 
математику учить в школе надо было

Добавлено через 1 минуту и 20 секунд

бред какой %)

Может и бред... раздел для новичков)   

 

Снежанна, какой пример? как среднее арифметическое считать? я как-то забыл как это делается, потому не могу написать, и учебника за 5й класс под рукой нету =\

Мне понять как это в программе осущетвить. А среднее арифмитическое могу напомнить   

а может он не просто так   


что-то мне это видится более чем не очевидно  

Добавлено через 8 минут и 28 секунд
или вы имели ввиду средневзвешенное?

расстояние между двумя точками считается, как квадратный корень из суммы квадратов разностей координат: 

Добавлено через 2 минуты и 31 секунду

M bsa

Сообщения, не относящиеся к теме, удалил

когда-то писал, может пригодится: 
тут класс точки и класс прямой, прямая может возвращать расстояние между точками, которыми задана, tg угла наклона и смещение, те короче
y=kx+b, она может вернуть k, b, а также расстояние между точками, которыми задана...
<myline.h>


а это <mypoint.h>

Признаю я был не прав. Среднее арифметическое там не подходит хотя бы потому что оно выдает точку не обязательно принадлежащую к множеству заданных точек.
Однако я заметил что C++ убило мозг участников форума, т.к. никто так и не попытался решить задачу математически.
При беглом анализе, очевидно что для вырожденного случая с 2я точками обе точки являются решениями, также точки могут совпадать друг с другом. Для вырожденного случая когда все точки находятся на одной прямой, если число точек нечетно, решением является "средняя" точка, если четно - две "средние" точки. Я не проверял, но с большой долей вероятности "средней" точкой является точка ближайшая к центру масс, т.е. к среднему арифметическому координат точек.

Наоборот. Мозг ищет более рациональное решение. Мне, допустим, легче сначала решить эту задачу программно в лоб, а потом, если время позволит произвести анализ решения.