최대 우회율

여기서 다루는 기하 그래프 $G = (V, E)$는 정점 $N$개가 한 줄로 이어진 경로다. 정점은 $v_1, v_2, \ldots, v_N$이고, $1 \le i \le N-1$인 모든 $i$에 대해 $v_i$와 $v_{i+1}$을 잇는 간선이 있다. 각 정점은 평면 위의 한 점이고, 각 간선은 그 두 점을 잇는 선분이다.

$G$를 간선 위로만 다닐 수 있는 도로망이라고 하자. 한 정점에서 다른 정점으로 갈 때 실제로 지나는 거리는 두 점을 곧게 이은 거리보다 길어지기 마련이고, 우회율은 그 비를 나타낸다. $i < j$인 두 정점 $v_i$와 $v_j$의 우회율은 다음과 같다.

$D(G, v_i, v_j) = d_G(v_i, v_j) / d(v_i, v_j)$

여기서 $d(p, q)$는 두 점 $p$와 $q$ 사이의 유클리드 거리이고, $d_G(v_i, v_j) = d(v_i, v_{i+1}) + d(v_{i+1}, v_{i+2}) + \ldots + d(v_{j-1}, v_j)$는 경로를 따라 이동한 길이다. $G$의 최대 우회율 $D(G)$는 서로 다른 두 정점으로 만들 수 있는 모든 쌍의 우회율 중 가장 큰 값이다.

위 그림은 정점 7개로 이루어진 경로 $G$이다. 그림에 적힌 수는 두 점 사이의 유클리드 거리라서 $d(v_1, v_2) = 10$이고 $d(v_1, v_4) = 4$이다. 따라서 $D(G, v_1, v_4) = d_G(v_1, v_4) / d(v_1, v_4) = (10 + 10 + 9) / 4 = 29 / 4$이다.

경로를 이루는 점 $N$개가 순서대로 주어진다. 최대 우회율 $D(G)$를 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$($1 \le T \le 20$)가 주어진다. 각 테스트 케이스의 첫째 줄에는 정점의 개수 $N$($2 \le N \le 10000$)이 주어지고, 이어지는 $N$개 줄에 $v_1, v_2, \ldots, v_N$의 좌표가 순서대로 한 줄에 하나씩 주어진다. 한 줄에 있는 두 정수는 공백 하나로 구분한다. 모든 좌표는 $-10000$ 이상 $10000$ 이하의 정수다. 이웃한 두 정점이 같은 점인 경우는 없으므로 모든 간선의 길이는 0보다 크다.

각 테스트 케이스마다 한 줄씩 출력한다.

$D(G)$가 1000 이상이면 TOO LARGE를 출력한다. 그렇지 않으면 $D(G)$를 소수점 아래 셋째 자리에서 반올림해 소수점 아래 두 자리까지 출력한다. 두 자리는 항상 채워서 쓴다. 예를 들어 1이 아니라 1.00으로 출력한다.

경로는 스스로 교차할 수 있다. 이웃하지 않은 두 정점이 같은 점에 놓일 수도 있는데, 이때는 두 점 사이의 거리가 0이라서 $D(G)$가 무한히 커지므로 TOO LARGE를 출력한다.

모든 테스트 케이스에서 $D(G)$의 정확한 값은 1000에서 $10^{-6}$보다 멀리 떨어져 있고, 0.005, 0.015, 0.025처럼 0.01의 배수 사이 한가운데에 놓인 값에서도 $10^{-6}$보다 멀리 떨어져 있다. 반올림 방향이 애매한 경우는 없다.