CF659D.Bicycle Race
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Maria participates in a bicycle race.
The speedway takes place on the shores of Lake Lucerne, just repeating its contour. As you know, the lake shore consists only of straight sections, directed to the north, south, east or west.
Let's introduce a system of coordinates, directing the Ox axis from west to east, and the Oy axis from south to north. As a starting position of the race the southernmost point of the track is selected (and if there are several such points, the most western among them). The participants start the race, moving to the north. At all straight sections of the track, the participants travel in one of the four directions (north, south, east or west) and change the direction of movement only in bends between the straight sections. The participants, of course, never turn back, that is, they do not change the direction of movement from north to south or from east to west (or vice versa).
Maria is still young, so she does not feel confident at some turns. Namely, Maria feels insecure if at a failed or untimely turn, she gets into the water. In other words, Maria considers the turn dangerous if she immediately gets into the water if it is ignored.
Help Maria get ready for the competition — determine the number of dangerous turns on the track.
玛丽亚参加一场自行车比赛。
赛道位于卢塞恩湖畔,完全沿湖岸线铺设。众所周知,湖岸线仅由若干直线段组成,且每段直线的方向仅为北、南、东或西之一。
我们建立一个坐标系:Ox 轴由西指向东,Oy 轴由南指向北。比赛的起点选为赛道上最南端的点(若存在多个这样的点,则取其中最西边的那个)。参赛者从该起点出发,初始行进方向为正北。在赛道的所有直线段上,参赛者始终朝四个基本方向之一(北、南、东、西)行进,并且仅在直线段之间的弯道处改变行进方向。当然,参赛者绝不会“掉头”,即不会将行进方向由北直接变为南,或由东直接变为西(反之亦然)。
玛丽亚尚且年幼,因此在某些弯道处缺乏信心。具体而言,若她在某个弯道处未能及时或正确转弯,便会驶入水中——玛丽亚将此类弯道视为“危险弯道”。换言之,若忽略该弯道,她将立即驶入水中,则该弯道即为危险弯道。
请帮助玛丽亚为比赛做好准备——确定赛道上危险弯道的数量。
输入格式
The first line of the input contains an integer n (4 ≤ n ≤ 1000) — the number of straight sections of the track.
The following (n + 1)-th line contains pairs of integers (x__i, y__i) ( - 10 000 ≤ x__i, y__i ≤ 10 000). The first of these points is the starting position. The i-th straight section of the track begins at the point (x__i, y__i) and ends at the point (x__i + 1, y__i + 1).
It is guaranteed that:
- the first straight section is directed to the north;
- the southernmost (and if there are several, then the most western of among them) point of the track is the first point;
- the last point coincides with the first one (i.e., the start position);
- any pair of straight sections of the track has no shared points (except for the neighboring ones, they share exactly one point);
- no pair of points (except for the first and last one) is the same;
- no two adjacent straight sections are directed in the same direction or in opposite directions.
输入的第一行包含一个整数 n(4≤n≤1000),表示赛道中直线段的数量。
接下来的 n+1 行,每行包含一对整数 (xi,yi)(−10000≤xi,yi≤10000)。其中第一个点为起始位置。赛道的第 i 段直线段起始于点 (xi,yi),终止于点 (xi+1,yi+1)。
保证满足以下条件:
- 第一段直线段的方向为正北;
- 赛道的最南端点(若存在多个最南端点,则取其中最西边的一个)即为第一个点;
- 最后一个点与第一个点重合(即回到起始位置);
- 任意两条非相邻的直线段之间无公共点(相邻直线段恰好共享一个端点);
- 除第一个点与最后一个点外,其余任意两点均不相同;
- 任意两条相邻直线段的方向既不相同,也不相反。
输出格式
Print a single integer — the number of dangerous turns on the track.
输出一个整数——赛道上危险弯道的数量。
输入输出样例
输入#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
说明/提示
The first sample corresponds to the picture:

The picture shows that you can get in the water under unfortunate circumstances only at turn at the point (1, 1). Thus, the answer is 1.
第一个样例对应下图:

该图表明,你仅可能在不幸的情况下于点 (1,1) 处转弯时进入水中。因此,答案为 1。
输入解题思路,AI测评打分。不知道怎么写?