Выпуклая оболочка: различия между версиями
Материал из Algocode wiki
Строка 24: | Строка 24: | ||
[[Онлайн выпуклая оболочка]] | [[Онлайн выпуклая оболочка]] | ||
+ | |||
+ | == Что делать, если не сдаётся задачка на выпуклую оболочку == | ||
+ | * Проверьте, что ваш код корректно обрабатывает совпадающие точки | ||
+ | * Проверьте, что ваш код корректно обрабатывает точки, лежащие на одной прямой, особенно если это прямая, содержащая одну из сторон оболочки | ||
+ | * Отдельно проверьте, что вы правильно находите точки, лежащие на последней стороне, если вы пишете алгоритм Грэхема | ||
{{Автор|Глеб Лобанов|glebodin}} | {{Автор|Глеб Лобанов|glebodin}} | ||
+ | {{Автор|Александр Гришутин|rationalex}} | ||
+ | |||
[[Категория:Конспект]] | [[Категория:Конспект]] |
Версия 12:32, 18 февраля 2022
Содержание
Определения
Выпуклое множество - такое множество точек, что все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству
Выпуклая оболочка фигуры - такое выпуклое множество точек, что все точки фигуры также лежат в нем.
Минимальная выпуклая оболочка фигуры - это минимальная по площади выпуклая оболочка.
Задача
Дано множество точек, требуется построить его минимальную выпуклую оболочку.
Алгоритм Джарвиса(Метод заворачивания подарка)
Дополнительно
Что делать, если не сдаётся задачка на выпуклую оболочку
- Проверьте, что ваш код корректно обрабатывает совпадающие точки
- Проверьте, что ваш код корректно обрабатывает точки, лежащие на одной прямой, особенно если это прямая, содержащая одну из сторон оболочки
- Отдельно проверьте, что вы правильно находите точки, лежащие на последней стороне, если вы пишете алгоритм Грэхема
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex