Помогите, пожалуйста, решить задачу на c++!

Darina
Сообщения: 2
Зарегистрирован: 02 июн 2017, 14:13

02 июн 2017, 14:24

Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна.
Аватара пользователя
Сионист
Сообщения: 1077
Зарегистрирован: 31 мар 2014, 06:18

02 июн 2017, 17:42

А здесь то чего сложного? Двойной цикл и ни каких гвоздёв.
Писать можно на чём угодно, но зачем же так себя ограничивать? Пиши на c.
Слива
Сообщения: 133
Зарегистрирован: 19 мар 2016, 10:15

02 июн 2017, 18:42

Не такая уж и простая задача на самом деле. Ну если же Вы знаете ответ, то напишите, пожалуйста.
Слива
Сообщения: 133
Зарегистрирован: 19 мар 2016, 10:15

02 июн 2017, 19:38

Кстати! Пишут, что только для 3 точек можно найти центр. Я, как профессионал, думаю, что это правда.
Слива
Сообщения: 133
Зарегистрирован: 19 мар 2016, 10:15

02 июн 2017, 19:39

Для 4 точек уже центр не находится. Верно товарищи?
Аватара пользователя
AiK
Сообщения: 2273
Зарегистрирован: 13 фев 2004, 18:14
Откуда: СПб
Контактная информация:

02 июн 2017, 19:52

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

Нет. На окружности можно отметить произвольное количество точек и ото всех них до центра будет минимальное расстояние :)
Даже самый дурацкий замысел можно воплотить мастерски
Слива
Сообщения: 133
Зарегистрирован: 19 мар 2016, 10:15

02 июн 2017, 20:07

Ну это когда строго окружность, я имел ввиду для случайных точек, используйте функцию rand() в своих умозаключениях.
http://baumanki.net/show-document/1-591 ... a3031dd/2/ - Рис. 7. Из этого рисунка и из других статей следует, что центр треуготльника лежит на пересечении серединных перпендикуляров.
Аватара пользователя
AiK
Сообщения: 2273
Зарегистрирован: 13 фев 2004, 18:14
Откуда: СПб
Контактная информация:

03 июн 2017, 02:14

Слива писал(а):используйте функцию rand() в своих умозаключениях.
А вы в таком случае используйте условие задачи :) Нет задачи найти центр для четырёх и более произвольных точек. Есть задача найти из N точек максимально близкую от центра.
Даже самый дурацкий замысел можно воплотить мастерски
Слива
Сообщения: 133
Зарегистрирован: 19 мар 2016, 10:15

03 июн 2017, 06:17

Есть один вариант решения. Не знаю подойдет или нет, но в общем смысл в следующем. Находятся MinX, MaxX, MinY, MaxY - коробка или границы в которой лежат все точки. Это прямоугольник. Потом находится центр этого прямоугольника. Это и будет искомая точка. Верно?
Аватара пользователя
AiK
Сообщения: 2273
Зарегистрирован: 13 фев 2004, 18:14
Откуда: СПб
Контактная информация:

03 июн 2017, 15:33

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

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

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