다각형의 확장 > 문제은행

본문 바로가기


문제은행

1043 : 다각형의 확장

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 6 회    시도횟수: 22 회   



n개의 꼭지점들과 수평선분 및 수직선분들로 구성된 꼭지점들의 좌표가 주어질 때 다음과 같이 표현될 수 있다.

 

다각형 = {(X1, Y1), (X2, Y2), ..., (Xn, Yn)}

여기서 (X1, Y1)은 맨 아래 가장 왼쪽에 있는 꼭지점의 좌표이며, 그 다음 좌표들은 (X1, Y1)에서 반시계방향으로 다각형의 둘레를 따라 돌면서 만나는 꼭지점들의 좌표들을 차례로 쓴 것이다.

 

예를 들어 아래의 그림에서 안에 들어 있는 빗금 친 다각형은 다음과 같이 표현된다.
{(5, 5), (17, 5), (15, 13), (14, 13), (14, 8), (8, 11), (9, 11), (9, 13), (5, 13)}

 

다각형이 주어졌을 때 이 다각형의 d- 확장은 주어진 다각형의 둘레를 돌면서 d만큼 바깥쪽으로 확장시키는 것을 말한다.

예를 들어 빗금 친 다각형을 2-  확장시키면 아래 그램에서 밖에 있는 다각형, 즉 {(3, 3), (19, 3), (19, 15), (12, 15), (12, 10), (11, 10), (11, 15), (3, 15)}가 된다.

 

 7a237fa5da1383e7c81a70d669331bd9_1469010 

 

이 때, d- 확장에 의해 공간이 메워져서 꼭지점의 개수가 변할 수 있다. 단, d- 확장에 의해서 아래의 예와 같이 다각형 안에 구멍이 생기는 경우는 없다고 가정한다.

 

 7a237fa5da1383e7c81a70d669331bd9_1469010

 

입력으로 d 값과 다각형이 주어질 때 d- 확장된 다각형을 구하는 프로그램을 작성하라.


 


첫 번째 줄에는 d 가 주어지고, 그 다음 줄에는 n이 주어진다.
그 다음 n개의 줄에 다각형을 나타내는 n개의 좌표가 주어진다. 여기서 1 <= d <= 200 이고, 1<= n <= 50 이며, X, Y 좌표값은 2000 이하의 자연수로 한다.


확장된 다각형의 꼭지점의 개수와 좌표들을 맨 아래 가장 왼쪽 꼭지점부터 반시계방향으로 출력한다.

[Copy]
2
10
5 5
17 5
17 13
14 13
14 8
8 8
8 11
9 11
9 13
5 13
[Copy]
8
3 3
19 3
19 15
12 15
12 10
11 10
11 15
3 15





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.