터널 속의 광선

시간 제한1초메모리 제한128 MB

요약
단위 높이 터널의 바닥 꼭짓점들이 주어질 때, 연속한 변환기 사이의 직선 광선이 터널 안에 엄격히 머물도록 하는 최소 변환기 수를 구한다.
난이도

보통10점 중 7점

유형
기하, 그리디, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

정사각형(높이 11) 단면을 가진 터널이 n−1n-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(2≤N≤10002 \le N \le 1000)이 주어집니다. 다음 NN개의 줄에는 각각 두 수 xix_i와 yiy_i(−10000≤xi,yi≤10000-10000 \le x_i, y_i \le 10000), 즉 ii번째 바닥 꼭짓점의 좌표가 주어집니다. xix_i는 강한 증가 순서로 주어집니다.

출력

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

예제4

  1. 예제 1

    입력
    4
    1 1
    2 1
    3 2
    4 1
    
    예상 출력
    1
    
  2. 예제 2

    입력
    5
    1 1
    2 1
    3 2
    4 1
    5 2
    
    예상 출력
    2
    
  3. 예제 3

    입력
    2
    0 0
    5 0
    
    예상 출력
    0
    
  4. 예제 4

    입력
    5
    1 3
    2 3
    3 3
    4 3
    5 3
    
    예상 출력
    0