곡선 자르기

컴퓨터 그래픽 캔버스는 컴퓨터 화면에서 그림을 그릴 수 있는 직사각형 영역을 말한다. 캔버스는 2차원 좌표 평면처럼 각 점의 위치를 좌표로 표시한다. 캔버스의 정중앙 점이 원점 (0,0)이고, 오른쪽으로 갈수록 \(x\)좌표 값이 커지고, 위쪽으로 갈수록 \(y\)좌표 값이 커진다.

창수는 마우스를 이용하여 캔버스에 그림을 그리고 있다. 지금은 캔버스에 곡선을 그리는데, 시작점과 끝점이 붙어있는 것 외에는 중간에 선이 교차하거나 붙는 경우가 없다. 곡선을 다 그린 다음, 캔버스에서 \(x\)축의 아래쪽 영역을 깨끗이 지우면 아래 그림처럼 경계선이 서로 만나지 않는 봉우리들의 패턴이 나타난다. 여기서 봉우리는 시작점과 끝점이 \(x\)축 상에 있는 곡선 부분과 \(x\)축으로 둘러싸인 영역을 말한다. 아래 그림의 예에서는 5개의 봉우리가 나타난다.

마우스로 그린 곡선은 컴퓨터에 의해 수직 선분과 수평 선분들로 구성된 경로의 형태로 메모리에 저장된다. 따라서 창수가 그린 곡선의 경우는 수평 선분과 수직 선분이 한 번씩 번갈아가며 이어진 경계선을 가진 직교다각형의 형태로 저장된다. 이 직교다각형의 모든 꼭짓점은 서로 다르며, 연속한 두 변 이외에는 어떤 두 변도 만나지 않는다. 직교 다각형의 형태로 변환된 예를 아래 그림에서 볼 수 있다.

창수는 이 직교다각형을 입력으로 받아 \(x\)축의 위쪽 영역에 나타나는 봉우리들 중에서, 다른 봉우리에 의해 포함되지 않는 봉우리 개수와 다른 봉우리를 포함하지 않는 봉우리 개수를 구하는 프로그램을 작성하려고 한다. 위 그림에서는 다른 봉우리에 의해 포함되지 않는 봉우리 개수는 3이고 다른 봉우리를 포함하지 않는 봉우리 개수는 4이다.

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 곡선을 표현하는 직교다각형의 꼭짓점의 개수 \(N(4 \le N \le 10^{6})\)이 주어진다. 다음 \(N\)개의 각 줄에는 직교다각형의 경계선을 따라갈 때 만나는 꼭짓점 순서대로 각 꼭짓점의 좌표가 주어진다. 이 순서의 방향은 가장 왼쪽에 있는 수직 선분인 변을 볼 때 아래에서 위로 올라가는 방향이다. 각 좌표는 \(x\)좌표와 \(y\)좌표가 공백을 사이에 두고 주어지며, \(x\)좌표와 \(y\)좌표 모두 -\(10^{9}\) 보다 크거나 같고 \(10^{9}\)보다 작거나 같다. 또한 \(y\)좌표가 0인 경우는 없으며 \(x\)축과 교차하는 변이 반드시 하나 이상 존재한다.

표준 출력으로, 입력으로 주어진 직교다각형에 의해서 나타나는 봉우리 패턴에서 다른 봉우리에 의해 포함되지 않는 봉우리 개수와 다른 봉우리를 포함하지 않는 봉우리 개수를 공백을 사이에 두고 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2017 > 2차 대회 > 중등부 2번