Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Fox_Yo
0 / 0 / 0
Регистрация: 31.10.2013
Сообщений: 86
#1

Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества - C++

20.03.2014, 17:43. Просмотров 734. Ответов 3
Метки нет (Все метки)

Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества, то есть выпуклый многоугольник с вершинами в некоторых точках этого множества, охватывающий все точки. Если честно даже не представляю как ее делать, помогите пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.03.2014, 17:43     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
Посмотрите здесь:

найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости) C++
Найти такую точку заданного на плоскости множества точек, сумма расстояний от которой до остальных минимальна C++
C++ Найти точку на плоскости, сумма расстояний от которой до остальных точек множества максимальна
C++ Множество точек на плоскости
C++ Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
C++ На плоскости задано множество точек. Выбрать три различные точки так, чтобы проходящая через них окружность делила это множество на группы
C++ Дана точка A и множество B из N точек. Найти номер точки из множества B, наиболее удаленной от точки A
Дано множество точек на плоскости C++
Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую C++
C++ Дано множество точек на плоскости. Необходимо найти 4 точки (с максимальными и минимальными значениями x и y)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
Эксперт C
 Аватар для Байт
15074 / 9476 / 1389
Регистрация: 24.12.2010
Сообщений: 17,541
21.03.2014, 10:04     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества #2
Цитата Сообщение от Fox_Yo Посмотреть сообщение
не представляю как ее делать
Проводим n(n-1)/2 прямых через все возможные пары точек. Для каждой прямой: Если все оставшиеся точки лежат по одну сторону - наша прямая есть часть искомого многоугольника.
Как проверить по какую сторону лежат точки? Если при подстановке в уравнение прямой Ax+Bx+C получается одинаковый знак - по одну, иначе по разные.
Удобная проверка одно-разнозначности 2-х чисел: if (a*b < 0) ...
Fox_Yo
0 / 0 / 0
Регистрация: 31.10.2013
Сообщений: 86
21.03.2014, 10:42  [ТС]     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества #3
Байт, Я даже рисунок рисовал, вообще не представляю, можешь более подробно объяснить, питался искать в инете про многоугольники, и тоже не то. Ну спасибо хоть что ответил.
Байт
Эксперт C
 Аватар для Байт
15074 / 9476 / 1389
Регистрация: 24.12.2010
Сообщений: 17,541
21.03.2014, 11:36     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества #4
Цитата Сообщение от Fox_Yo Посмотреть сообщение
можешь более подробно объяснить
Что именно непонятно? Это все элементарная аналитическая геометрия.
Что значит "подробно объяснить"? Написать прогу? Прости, недосуг. То, что может вызвать затруднения в математической части, я написал. Далее, человек владеющий азами программирования (или пытающийся ими овладеть), ИМХО, должен хотя бы попытаться написать код.
Yandex
Объявления
21.03.2014, 11:36     Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
Ответ Создать тему
Опции темы

Текущее время: 09:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru