Уточнение этого
Уточнение этого факта приводит к алгоритму с временем работы, пропорциональным О(N2). Рисунок, приводимый ниже, может быть, поможет Вам в разработке этого алгоритма. Обратите внимание на то, что в некоторый момент времени необходимо изменить направление оси X, т.е. считать углы относительно отрицательного направления оси X.
Третий метод. Идея. Разбиваем множество S из N точек на два подмножества, каждое из которых будет содержать одну из двух ломаных, соединение которых даст многоугольник выпуклой оболочки. Найдем точки w и r, имеющие соответственно наименьшую и наибольшую абсциссы. Проведем через них прямую L, тем самым получив разбиение множества точек S на два подмножества S1 (выше или на прямой L) и S2 (ниже прямой L). Определим точку h, для которой треугольник <whr> имеет наибольшую площадь среди всех треугольников {<wpr>:p?S1}. Если точек имеется более одной, то выбирается та из них, для которой угол <hwr> наибольший. Точка h гарантированно
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
