삼각형으로 자르기
시간 제한2초메모리 제한128 MB
꼭짓점을 하나씩 잘라내어 삼각형이 될 때까지 줄이는 볼록다각형에서, 남을 수 있는 삼각형의 최대 넓이를 구하는 문제입니다.
문제
볼록 다각형이 주어진다. 현재 다각형에서 연속한 세 꼭짓점을 고르고, 그 세 꼭짓점으로 이루어진 삼각형을 잘라낸다. 잘라낸 뒤에는 선택한 세 꼭짓점 중 가운데 꼭짓점이 사라진 것과 같아서, 꼭짓점이 하나 줄어든 새로운 볼록 다각형이 남는다.
이 과정을 남은 다각형이 삼각형이 될 때까지 반복한다. 자르는 순서에 따라 마지막에 남는 삼각형은 달라질 수 있다.
마지막에 남길 수 있는 삼각형의 넓이 중 최댓값을 구하라.
입력
첫째 줄에 볼록 다각형의 꼭짓점 수 N이 주어진다. (3 <= N <= 35)
둘째 줄부터 N개의 줄에 걸쳐 각 꼭짓점의 좌표 x, y가 시계 방향 순서로 주어진다. 모든 좌표는 10,000 이하의 자연수이다.
출력
첫째 줄에 마지막에 남길 수 있는 삼각형 넓이의 최댓값을 출력한다. 절대 오차 또는 상대 오차가 10^-9 이하이면 정답으로 인정된다.