Цитата(Fanat @ 20.12.2008 14:08)
алгоритм (наверно, скорее формулу) определения находятся ли все (допустим 3) вектора в одной полуплоскости.
Нет, скорее алгоритм
.
Идешь в цикле по всем векторам
Ai.
Производишь поворот системы координат (от исходного положения) на угол, который текущий вектор
Ai составляет с осью Х. После такого поворота его Y-компонента занулится:
(A
ix, A
iy) -> (A
ix', 0) .
Все остальные вектора также подвергнутся преобразованию:
(A
jx, A
jy) -> (A
jx', A
jy') .
Проходишь в цикле по всем остальным (кроме i-того и последнего) векторам и смотришь произведение:
m
j = A
jy' * A
j+1y'
Если все такие произведения неотрицательны:
m
j <=0 ,
то все вектора лежат в одной полуплоскости, причем сечение плоскости производится вектором
Ai. Если нет - продолжить внешний цикл.
Вроде так. Замучился индексы проставлять..