← 返回题目列表

Codeforces · 659/D

D. 自行车比赛

中文机器翻译题面 查看原题

玛丽亚参加自行车比赛。

高速公路位于卢塞恩湖畔,只是重复其轮廓。如您所知,湖岸仅由笔直的部分组成,分别指向北、南、东或西。

让我们介绍一个坐标系,Ox 轴从西向东,Oy 轴从南向北。选择赛道的最南端作为比赛的起始位置(如果有多个这样的点,则选择其中最西端的点)。参赛者开始比赛,向北移动。在赛道的所有直线部分,参与者沿四个方向(北、南、东或西)之一行进,并且仅在直线部分之间的弯道处改变运动方向。当然,参与者永远不会回头,也就是说,他们不会改变从北到南或从东到西(反之亦然)的运动方向。

玛丽亚还年轻,所以她在某些时候没有自信。也就是说,如果玛丽亚在失败或不合时宜的转弯时掉入水中,她就会感到不安全。换句话说,如果忽视这一点,玛丽亚会立即下水,她认为转弯是危险的。

帮助玛丽亚为比赛做好准备 - 确定赛道上危险转弯的数量。

输入

输入的第一行包含一个整数 n (4 ≤ n ≤ 1000) — 轨道直线部分的数量。

以下第 (n + 1) 行包含整数对 (xi, yi) (- 10 000 ≤ xi, yi ≤ 10 000)。第一个点是起始位置。轨道的第 i 个直线段从点 (xi, yi) 开始,到点 (xi + 1, yi + 1) 结束。

保证:

- 第一个直线段指向北;
- 轨迹的最南端(如果有多个,则其中最西端)点是第一个点;
- 最后一个点与第一个点重合(即起始位置);
- 轨道上的任何一对直线段都没有共享点(除了相邻的直线段外,它们仅共享一个点);
- 没有一对点(除了第一个和最后一个)是相同的;
- 没有两个相邻直线段的方向相同或相反。

输出

打印一个整数——赛道上危险转弯的次数。

示例

输入 #1

6
0 0
0 1
1 1
1 2
2 2
2 0
0 0

输出 #1

1

输入 #2

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

输出 #2

6

注意

第一个样本对应图片:

图为不幸情况下只能在点(1, 1)处转弯才能下水。因此,答案是1。