곡선 자르기 > 문제은행

본문 바로가기


문제은행

3076 : 곡선 자르기

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 0회    시도횟수: 0회    채점준비중입니다.



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

 

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

08b6f023ea4f0ddc33a2459594e06b23_1502449 

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

08b6f023ea4f0ddc33a2459594e06b23_1502449
 

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


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


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

부분문제의 제약 조건
● 부분문제 1: 전체 점수 100점 중 11점에 해당하며 N≤1,000 이고 입력으로 주어지는 꼭짓점의 x좌표와 y좌표는 -1,000 보다 크거나 같고 1,000 보다 작거나 같다.
● 부분문제 2: 전체 점수 100점 중 24점에 해당하며 N≤10,000 이다.
● 부분문제 3: 전체 점수 100점 중 65점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
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
[Copy]
1 2


[Copy]
4 
1 1 
1 -1 
-1 -1 
-1 1
[Copy]
1 1



[도움말 보기]


HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.