시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB452191658823.380%

문제

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

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

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

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

입력

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

출력

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

서브태스크

번호배점제한
111

N ≤ 1,000이고 입력으로 주어지는 꼭짓점의 x좌표와 y좌표는 -1,000보다 크거나 같고 1,000보다 작거나 같다.

224

N ≤ 10,000

365

원래의 제약조건 이외에 아무 제약조건이 없다.

예제 입력 1

14
-4 -4
-4 3
3 3
3 -2
1 -2
1 1
-1 1
-1 -1
-2 -1
-2 2
-3 2
-3 -2
0 -2
0 -4

예제 출력 1

1 2

예제 입력 2

4
1 1
1 -1
-1 -1
-1 1

예제 출력 2

1 1

힌트

※ 입력(1)의 직교다각형을 그림으로 나타내면 아래와 같다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.