| Codeforces Round 346 (Div. 2) |
|---|
| Закончено |
Мария участвует в велосипедной гонке.
Гоночная трасса проходит по берегу озера Люцерн, точно повторяя его контур. Как известно, берег озера состоит только из прямых участков, направленных на север, юг, восток или запад.
Введём систему координат, направив ось Ox с запада на восток, а ось Oy — с юга на север. В качестве позиции старта гонки выбирается самая южная (а если таких несколько, то самая западная из них) точка трассы. Участники начинают гонку, двигаясь на север. На всех прямых участках трассы участники едут в одном из четырёх направлений (север, юг, восток или запад) и меняют направление движения только на поворотах между прямыми участками. Участники, конечно, никогда не поворачивают назад, то есть не меняют направление движения с северного на южное или с восточного на западное (или наоборот).
Мария ещё юна, поэтому она чувствует себя уверенно не на всех поворотах. А именно, Мария чувствует себя неуверенно, если при неудачном или несвоевременном повороте она попадёт в воду. Иными словами, Мария считает поворот опасным, если при его игнорировании она сразу попадает в воду.
Помогите Маше подготовиться к соревнованию — определите количество опасных поворотов на трассе.
В первой строке входных данных находится целое число n (4 ≤ n ≤ 1000) — количество прямых участков трассы.
В следующих (n + 1)-й строке находятся пары целых чисел (xi, yi) ( - 10 000 ≤ xi, yi ≤ 10 000). Первая из этих точек является позицией старта. i-й прямой участок трассы начинается в точке (xi, yi) и заканчивается в точке (xi + 1, yi + 1).
Гарантируется, что:
- первый прямой участок направлен на север;
- самая южная (а если таких несколько, то самая западная из них) точка трассы — первая точка;
- последняя точка совпадает с первой (то есть с позицией старта);
- любая пара прямых участков трассы не имеет общих точек (за исключением соседних, имеющих ровно одну общую точку);
- никакая пара точек (кроме первой и последней) не совпадает;
- никакие два соседних прямых участка не направлены в одну и ту же сторону или в противоположные стороны.
Выведите единственное целое число — количество опасных поворотов на трассе.
6
0 0
0 1
1 1
1 2
2 2
2 0
0 0
1
16
1 1
1 5
3 5
3 7
2 7
2 9
6 9
6 7
5 7
5 3
4 3
4 4
3 4
3 2
5 2
5 1
1 1
6
Первый пример соответствует картинке:
На картинке видно, что оказаться в воде при неудачном стечении обстоятельств можно только на повороте в точке (1, 1). Таким образом, ответ равен 1.
