и есть искомое решение. Второй
и есть искомое решение.
Второй способ. Задача заключается в построении выпуклой оболочки множества точек на плоскости. Рассмотрим методы построения выпуклых оболочек (в конспективном виде).
Предварительные замечания. Q-выпуклый многоугольник. Вершины выпуклого многоугольника упорядочены по полярным углам относительно любой внутренней точки. Такая точка t находится путем взятия центра масс вершин треугольника, образованного любой тройкой вершин Q. Задача. Дана точка p и выпуклый N-угольник Q. Определить принадлежность точки p выпуклому N-угольнику Q.
Общая схема.
• Поиск клина. (Методом двоичного поиска. Утверждение. Точка p лежит между лучами, определяемыми qi и qi+1 тогда и только тогда, когда угол (ptqi+1) положительный, а угол (ptqi) отрицательный.)
• Сравнить p с единственным ребром. (Утверждение. Точка p внутренняя тогда и только тогда, когда угол (qiqi+1p) отрицательный.)
Первый метод. Алгоритм Грэхема. Идея. Тройки последовательных точек многократно проверяются в порядке
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
