볼록다각형(convexhull) > 문제은행

본문 바로가기


알고리즘 기하

1151 : 볼록다각형(convexhull)

제한시간: 2000 ms    메모리제한: 128 MB
해결횟수: 153 회    시도횟수: 527 회   



좌표평면에 여러개의 점들이 주어져 있다.
이 점들을 모두 포함하면서 넓이가 최소인 볼록다각형을 그리려고 할 때 볼록다각형의 넓이를 구하는 프로그램을 작성하시오.


첫 번째 줄에 점의 개수 N(4≤N≤100)이 주어진다.
두 번째 줄부터 N+1번째까지는 각 줄마다 두 개의 정수가 입력되는데 각 점의 x, y 좌표를 나타낸다. (-10,000≤x, y≤10,000)


볼록 다각형의 넓이를 소수 첫째 자리까지 출력하되 유효하지 않은 값은 출력하지 않는다. 예를 들어 20.0은 20으로 출력한다.

[Copy]
8
30 0
20 10
50 15
10 10
30 20
20 20
40 30
20 40
[Copy]
925


다각형의 넓이를 구하는 식(일명 사선식)은 다음과 같다.
다각형의 꼭지점을 연결하는 순서대로 각각의 좌표가 (x1, y1), (x2, y2), (x3, y3), (x4, y4)라고 할 때,


와 같은 식으로 구할 수 있다.



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.