볼록다각형(convexhull) > 문제은행 : 정보올림피아드&알고리즘



1151 : 볼록다각형(convexhull)

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
160 회   
시도횟수
505 회   

문제

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


입력형식

첫 번째 줄에 점의 개수 N(4≤N≤100)이 주어진다.

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


출력형식

볼록 다각형의 넓이를 소수 첫째 자리까지 출력하되 유효하지 않은 값은 출력하지 않는다.

예를 들어 20.0은 20으로 출력한다.


입력 예

8
30 0
20 10
50 15
10 10
30 20
20 20
40 30
20 40

출력 예

925

Hint!

단순 다각형의 넓이를 구하기

1. 벡터 외적 이용하기 

2. 사선식을 이용하기 : 방법 1과 본질적으로는 같은 내용이다. 

 

다각형의 꼭지점을 연결하는 순서대로 각각의 좌표가 (x1, y1), (x2, y2), (x3, y3), (x4, y4)라고 할 때,

 

 

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



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP