Выпуклая оболочка: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
 
(не показаны 2 промежуточные версии этого же участника)
Строка 24: Строка 24:
  
 
[[Онлайн выпуклая оболочка]]
 
[[Онлайн выпуклая оболочка]]
 +
 +
== Что делать, если не сдаётся задачка на выпуклую оболочку ==
 +
* Проверьте, что ваш код корректно обрабатывает совпадающие точки
 +
* Проверьте, что ваш код корректно обрабатывает точки, лежащие на одной прямой, особенно если это прямая, содержащая одну из сторон оболочки
 +
* Отдельно проверьте, что вы правильно находите точки, лежащие на последней стороне, если вы пишете алгоритм Грэхема
 +
* Выводите числа с плавающей точкой следующим образом:
 +
 +
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