Выпуклая оболочка
Содержание
Определения
Выпуклое множество - такое множество точек, что все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству
Выпуклая оболочка фигуры - такое выпуклое множество точек, что все точки фигуры также лежат в нем.
Минимальная выпуклая оболочка фигуры - это минимальная по площади выпуклая оболочка.
Задача
Дано множество точек, требуется построить его минимальную выпуклую оболочку.
Алгоритм Джарвиса(Метод заворачивания подарка)
Дополнительно
Что делать, если не сдаётся задачка на выпуклую оболочку
- Проверьте, что ваш код корректно обрабатывает совпадающие точки
- Проверьте, что ваш код корректно обрабатывает точки, лежащие на одной прямой, особенно если это прямая, содержащая одну из сторон оболочки
- Отдельно проверьте, что вы правильно находите точки, лежащие на последней стороне, если вы пишете алгоритм Грэхема
- Выводите числа с плавающей точкой следующим образом:
cout << fixed << setprecision(20) << ${YOUR_ANSWER_HERE} << endl;
setprecision фиксирует число выводимых цифр в числах с плавающей точкой, а fixed запрещает выводить числа в формате 3e7
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex