삼각분할

시간 제한1초메모리 제한128 MB

요약

볼록 다각형이 주어질 때 대각선 길이의 합이 최소가 되는 삼각분할을 찾아 소수 둘째 자리로 반올림해 출력한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 기하
정답자: 아직 제출이 없습니다

문제

평면 나라 플랫랜드에 큰 소동이 일어났다! 다가오는 해가 "삼각형의 해"가 될 것이라는 소문이 퍼지면서, 모든 주민이 세 개의 각으로 이루어진 물건을 하나쯤 가지려는 열풍에 휩싸였다. 이 유행은 특히 옷차림에서 가장 뚜렷하게 나타났다.

이 나라의 주민은 모두 볼록 다각형 모양이다. 각 주민은 자신의 몸(볼록 다각형)을 여러 개의 삼각형으로 나누는 옷, 이른바 "삼각분할"을 준비하고 있다. 삼각분할이란 다각형의 꼭짓점들을 잇는 대각선들의 집합으로, 이 대각선들은 (꼭짓점을 제외하고는) 서로 교차하지 않으며 다각형 전체를 삼각형들로 나눈다.

문제는 이 옷감의 각 띠가 두 꼭짓점을 잇는 대각선이어야 하고 매우 비싸다는 점이다. 삼각형을 어떻게 나누느냐에 따라 필요한 옷감의 총 길이가 달라진다. 따라서 주민들은 사용한 대각선들의 길이의 합이 가능한 한 작아지는 삼각분할을 찾고 싶어 한다. (다각형의 변은 옷감으로 세지 않으며, 오직 내부 대각선의 길이만을 더한다.)

각 볼록 다각형에 대해, 이 최소 대각선 길이의 합을 구하라.

입력

첫째 줄에 테스트 케이스의 수 $T$ ( $1 \le T \le 100$ )가 주어진다. 이어서 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 다각형의 꼭짓점 수 $N$ ( $3 \le N \le 100$ )이 주어진다. 다음 $N$ 개의 줄에는 다각형의 꼭짓점 좌표 $X$ , $Y$ ( $0 \le X, Y \le 10000$ )가 시계 방향 순서로 주어진다. (첫 꼭짓점은 임의로 선택된다.) 모든 다각형은 볼록 다각형임이 보장된다.

출력

각 테스트 케이스마다 한 줄에, 해당 다각형의 최소 삼각분할 길이(사용한 대각선 길이의 합)를 소수점 아래 둘째 자리까지 반올림하여 출력한다.

예제7

예제 1

입력

2
4
0.0 0.0
0.0 1.0
1.0 1.0
1.0 0.0
5
0.0 2.0
1.0 2.0
2.0 1.0
1.0 0.0
0.0 0.0

예상 출력

1.41
4.24

예제 2
입력
```
1
3
0 0
4 0
0 3
```
예상 출력
```
0.00
```
예제 3
입력
```
1
4
0 0
0 2
2 2
2 0
```
예상 출력
```
2.83
```
예제 4
입력
```
1
4
0 0
0 4
3 4
3 0
```
예상 출력
```
5.00
```
예제 5
입력
```
1
6
0 3
2 0
6 0
8 3
6 6
2 6
```
예상 출력
```
19.21
```

예제 6

입력

예상 출력

0.00
2.83
4.24

예제 7

입력

예상 출력

17.12