울타리 만들기 > 문제은행

본문 바로가기


실전대비 Level3

1256 : 울타리 만들기

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 31 회    시도횟수: 89 회   



로또에 당첨된 민우는 꿈에 그리던 섬을 하나 샀다. 섬은 직사각형으로 네모난 섬이고 그 섬에는 많은 큰 나무들이 여기 저기 자라고 있었다. 멋진 섬을 방문한 민우는 이 나무들의 모습을 보고 아주 좋은 생각을 해냈다. 그것은 바로 나무들을 이용하여 섬의 울타리를 만드는 것이다. 울타리는 섬에 자라는 많은 나무들을 모두 포함할 수 있는 위치에 자라는 나무들을 연결하여 울타리를 치는 것이다.

 

섬에 울타리를 치기 위해서 많은 나무들 중에 어떤 나무를 선택해야 하는지를 찾는 프로그램을 작성하시오. 단, 울타리는 볼록한 다각형의 형태를 가진다. 결코 오목하게 들어가는 부분이 없는 울타리를 만들어야 한다. 또한 나무들의 위치는 x축과 y축의 좌표 형식으로 표현될 수 있다.


첫째 줄에 주어지는 정점의 수로 정수 n(1≤n≤100)이 주어진다. 다음 줄에는 n줄 만큼의 정점의 좌표(1<x,y<10,000)가 주어진다.



첫째 줄에는 convexhull을 구성하는 정점의 수 h를 표시한다. 다음 줄부터 h줄 만큼 convexhull을 구성하는 정점들을 y좌표와 x좌표가 가장 작은 값을 시작으로 시계 반대방향으로 차례대로 표시한다.


[Copy]
10
2 6
3 9
4 4
4 8
5 2
6 7
7 6
7 8
9 3
10 6
[Copy]
6
5 2
9 3
10 6
7 8
3 9
2 6






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.