Сайт підготовки до олімпіади з інформатики

Обчислювальна геометрія

Література

Гісь І.В. Обчислювальна геометрія

Омелян П.П. Обчислювальна геометрія

Завдання та розв’язки ІІІ етапу Всеукраїнської учнівської олімпіади з інформатики в 2009-2010 н.р.

Другий тур

Задача VIОLАТION (20 балів)

В деякому місті шоферам заборонено при русі робити ліві повороти. За кожен такий поворот шофер повинен сплачувати штраф в розмірі М гривень. Для спостереження за рухом транспорту в місті встановлена комп'ютерна система, яка фіксує координати автомобіля на початку руху, в кінці та при кожному повороті.

Необхідно по заданій послідовності координат руху обчислити суму штрафу.

Вхідні дані: В першому рядку вхідного файлу VIOLATION.DAT записано N - кількість зафіксованих координат руху деякого автомобіля та М - величина штрафу, в наступних рядках координати автомобіля в процесі руху - (х_i, у_i), і=1,2,...,М, де (х₁, у₁) - точка початку руху, (х_N,у_N) - остання точка маршруту автомобіля.

Всі числа цілі та знаходяться в межах від -1000 до 1000.

Вихідні дані: Єдиний рядок вихідного файлу VIOLATION.SOL має містити суму штрафу.

Приклад:

Розв’язок

{Визначення координат векторів}

x[n+1]:=x[1];

y[n+1]:=y[1];

for i:=1 to n do begin

a[i]:=x[i+1]-x[i];

b[i]:=y[i+1]-y[i];

end;

{Підрахунок кількості додатних добутків}

a[n+1]:=a[1];

b[n+1]:=b[1];

k:=0;

for i:=1 to n do

if a[i]*b[i+1]-a[i+1]*b[i]>0 then k:=k+1;

{Виведення результату}

writeln(k)