터널 속의 광선

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

정사각형(높이 11) 단면을 가진 터널이 n1n-1개의 구간으로 이루어져 있습니다. 각 구간의 바닥은 곧은(기울어질 수 있는) 선분입니다. 점 [x1,y1],[x2,y2],,[xn,yn][x_1, y_1], [x_2, y_2], \dots, [x_n, y_n](x1<x2<<xnx_1 < x_2 < \dots < x_n)은 바닥이 시작하거나 끝나는 지점, 또는 두 구간이 만나는 지점을 나타냅니다. 천장은 바닥보다 정확히 11미터 위에 있으므로, 대응하는 천장의 꼭짓점은 [xi,yi+1][x_i, y_i + 1]입니다.

레이저 광선과 광 변환기가 표시된 터널의 단면

레이저 광선은 터널의 왼쪽 끝으로 들어와 오른쪽 끝까지 나아가야 하며, 항상 터널 내부에 엄밀히 머물러야 합니다(바닥이나 천장에 절대 닿을 수 없습니다).

광선의 방향을 바꾸기 위해 구간 경계에 광 변환기를 설치할 수 있습니다. 변환기는 들어온 광선을 흡수하고 원하는 방향으로 다시 내보내며, 다시 내보내는 광선은 들어온 광선이 도달한 지점이 아니라 그 경계 위의 임의의 점에서 출발할 수 있습니다. 변환기는 구간 경계에만 설치할 수 있으므로, 변환기의 가로 위치는 반드시 x1,x2,,xnx_1, x_2, \dots, x_n 중 하나여야 합니다.

두 변환기 사이(또는 터널의 끝과 변환기 사이)에서 광선은 직선으로 나아가며, 그 구간 전체에서 바닥과 천장 사이에 엄밀히 있어야 합니다.

광선이 터널 전체를 통과하는 데 필요한 광 변환기의 최소 개수를 구하세요.

입력

첫째 줄에 정수 NN(2N10002 \le N \le 1000)이 주어집니다. 다음 NN개의 줄에는 각각 두 수 xix_iyiy_i(10000xi,yi10000-10000 \le x_i, y_i \le 10000), 즉 ii번째 바닥 꼭짓점의 좌표가 주어집니다. xix_i는 강한 증가 순서로 주어집니다.

출력

필요한 광 변환기의 최소 개수를 나타내는 정수 하나를 출력합니다.