Лошадью ходи!(#1030) Почти Крэг Туми(#1032)
#1031

Задача g6_1031: Левые повороты (DOOI)
Маршрут движения автомобиля задан в виде координат вершин ломаной.
Необходимо определить количество левых поворотов (смежные участки ломаной не лежат на одной прямой). Автомобиль начинает движение с любой точки (!!!Здесь уточнение от меня - автомобиль начинает движение из первой вершины ломаной, а вот ее координаты любые!!!).
Формат входных данных:
Первая строка входного файла input.txt сомстоит из одного числа, количества звеньев ломаной; в последующих строках - пары натуральных чисел, координаты вершин ломаной.
Формат выходных данных:
Выходной файл output.txt содержит одно число - количество левых поворотов
input.txt:
4
1 1
2 2
3 2
3 3
2 3
output.txt:
2
Решение g6_1031:
Наконец-то геометрическая задача! (терпеть их не могу, если честно, но куда деваться). Звенья ломаной можно представить в виде векторов. А дальше я приведу кусок комментария Александра Николаевича Никитина:
Геометрические алгоритмы: С какой стороны вектора лежит точка?
Если 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 и т.д.

Наверх