컴퓨터 그래픽 캔버스는 컴퓨터 화면에서 그림을 그릴 수 있는 직사각형 영역을 말한다.

캔버스는 2차원 좌표 평면처럼 각 점의 위치를 좌표로 표시한다.

캔버스의 정중앙 점이 원점 (0,0)이고, 오른쪽으로 갈수록 x좌표 값이 커지고, 위쪽으로 갈수록 y좌표 값이 커진다.

창수는 마우스를 이용하여 캔버스에 그림을 그리고 있다.

지금은 캔버스에 곡선을 그리는데, 시작점과 끝점이 붙어있는 것 외에는 중간에 선이 교차하거나 붙는 경우가 없다.

곡선을 다 그린 다음, 캔버스에서 x축의 아래쪽 영역을 깨끗이 지우면 아래 그림처럼 경계선이 서로 만나지 않는 봉우리들의 패턴이 나타난다.

여기서 봉우리는 시작점과 끝점이 x축 상에 있는 곡선 부분과 x축으로 둘러싸인 영역을 말한다.

아래 그림의 예에서는 5개의 봉우리가 나타난다.

마우스로 그린 곡선은 컴퓨터에 의해 수직 선분과 수평 선분들로 구성된 경로의 형태로 메모리에 저장된다.

따라서 창수가 그린 곡선의 경우는 수평 선분과 수직 선분이 한 번씩 번갈아가며 이어진 경계선을 가진 직교다각형의 형태로 저장된다.

이 직교다각형의 모든 꼭짓점은 서로 다르며, 연속한 두 변 이외 에는 어떤 두 변도 만나지 않는다.

직교 다각형의 형태로 변환된 예를 아래 그 림에서 볼 수 있다.

창수는 이 직교다각형을 입력으로 받아 x축의 위쪽 영역에 나타나는 봉우리들 중에서,

다른 봉우리에 의해 포함되지 않는 봉우리 개수와 다른 봉우리를 포함하지 않는 봉우리 개수를 구하는 프로그램을 작성하려고 한다.

위 그림에서는 다른 봉우리에 의해 포함되지 않는 봉우리 개수는 3이고 다른 봉우리를 포함하지 않는 봉우리 개수는 4이다.

곡선 자르기 timer 1초 memory 512MB

곡선 자르기 1초 512MB