Задача 32: Левые повороты (DOOI)
Маршрут движения автомобиля задан в
виде координат вершин ломаной.
Необходимо определить количество левых поворотов (смежные участки
ломаной не лежат на одной прямой). Автомобиль начинает движение с
любой точки (!!!Здесь уточнение от меня - автомобиль начинает
движение из первой вершины ломаной, а вот ее координаты любые!!!).
Формат входных данных:
Первая строка входного файла input.txt сомстоит из одного числа,
количества звеньев ломаной; в последующих строках - пары натуральных
чисел, координаты вершин ломаной.
Формат выходных данных:
Выходной файл output.txt содержит одно число - количество
левых поворотов
input.txt:
4
1 1
2 2
3 2
3 3
2 3
output.txt:
2
Решение:
Наконец-то геометрическая задача! (терпеть их не могу, если честно,
но куда деваться). Звенья ломаной можно представить в виде векторов.
А дальше я приведу кусок комментария Александра Николаевича
Никитина:
Геометрические алгоритмы: С какой стороны вектора лежит точка?
Если vector(a) и vector(b) - вектора a и b соответственно, то:
vector(a)*vector(b) = ax*by - ay*bx = a*b*sin(beta-alfa)
ax,ay,bx,by - координаты концов векторов
a - длина вектора a
b - длина вектора b
alfa - угол альфа для вектора a
beta - угол бета для вектора b
Вывод: при общей начальной точке двух векторов их векторное
произведение больше нуля, если второй вектор направлен влево от
первого, и меньше нуля, если вправо.
Если известны две точки, то вектор, основанный на них можно получить
вычитанием двух векторов направленных из начала координат: например,
есть точка A и точка B
вектор|AB| = Вектор|B| - Вектор|A|, иным словом AB_x = Bx-Ax, AB_y=
By-Ay
Таким образом, получается:
Если есть вектор |AB|, заданный координатами ax,ay,bx,by и точка
px,py, то для того чтобы узнать лежит ли она слева или справа, надо
узнать знак произведения:
(bx-ax)*(py-ay)-(by-ay)*(px-ax)
Итак, вроде бы все понятно (сам прочитал первый раз в жизни - раньше
всегда брал готовую функцию). У нас есть два вектора 1-2 и 1-3 если
3 левее вектора 1-2, то поворот левый, иначе не левый (логично).
Точно также для вектора 2-3 и точки 4 и т.д.
Далее
ð
