ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102931
Темы:    [ Векторы ]
[ Задачи в пространстве ]
Сложность: 3
Классы:
Название задачи: Сумма штрафа .
В корзину
Прислать комментарий

Условие

Новый градоначальник города Глупова решил с целью пополнения бюджета и экономии горючего провести кампанию борьбы с левым уклоном и левыми рейсами. Для этого он запретил водителям выполнять левые повороты, установив штраф за каждый такой поворот в размере одного миллиона (разворот на 180o поворотом налево не считается). От тяжелого прошлого Глупову достались улицы, которые могут пересекаться под любыми углами. Градоначальник приказал установить компьютерную систему тотальной слежки, которая следит за каждым автомобилем, записывая его координаты каждый раз, когда тот меняет направление движения (включая начальную и конечную точки пути).

Требуется написать программу, вычисляющую по записанной последовательности координат автомобиля штраф, который должен быть взыскан с водителя.

Входные данные

В первой строке входного файла содержится целое число N – количество записанных пар координат (1 ≤ N ≤ 1000). В каждой из следующих N строк записана очередная из этих пар.

Выходные данные

Выведите в выходной файл суммарный штраф водителя в миллионах.

Пример входного файла

4
0 0
1 0
1 1
2 1

Пример выходного файла

1

Решение

Скачать архив тестов и решений

В этой задаче, фактически, необходимо определить, в каком направлении происходит кратчайший поворот от одного вектора (x1, y1) до другого вектора (x2, y2) – по часовой стрелке или против. Представим на время, что рассматриваемые вектора находятся не в плоскости, а в пространстве, и рассмотрим их векторное произведение. Оно будет иметь компоненты (0, 0, z), где z = x1y2 - x2y1. Тогда из определения векторного произведения получаем следующий полезный факт: рассматриваемый поворот осуществляется против часовой стрелки тогда и только тогда, когда x1y2 - x2y1 > 0.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 4
Название Вычислительная геометрия
Задача
Номер 1

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .