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