볼록 다각형 사각형 분할

볼록한 2N각형을 대각선으로 잘라 N-1개의 사각형으로 나눌 때, 자른 선분 길이의 합의 최솟값을 구한다.

보통7동적 계획법기하아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제2

문제

꼭짓점이 $2N$ 개인 볼록 다각형은 꼭짓점 쌍을 잇는 직선으로 $N-2$ 번 잘라 사각형 $N-1$ 개로 나눌 수 있다. 아래 그림은 $N = 5$ 인 다각형 하나를 서로 다른 세 가지 방법으로 나눈 결과다. 분할의 무게는 절단선 $N-2$ 개의 길이를 모두 더한 값이다. 무게가 가장 작은 분할의 무게를 구하라.

입력

첫째 줄에 정수 $N$ ( $2 \le N \le 100$ )이 주어진다. 이어지는 $2N$ 개의 줄에는 볼록 다각형 꼭짓점의 좌표 $X$ 와 $Y$ ( $0 \le X, Y \le 10000$ )가 소수점 넷째 자리까지, 반시계 방향 순서로 한 줄에 하나씩 주어진다.

출력

무게가 가장 작은 분할의 무게를 소수점 넷째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 네 자리는 값이 0이어도 모두 적는다.