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