우회 없애기

택배 회사는 자전거 라이더를 고용해 대도시 곳곳에 소포를 배달하고, 라이더에게는 이동한 총 거리에 비례해 배달료를 지급한다. 모든 회사 자전거에는 몇 초에 한 번씩 자신의 위치를 기록하는 GPS 장치가 달려 있다. 한 번의 배달에서 기록된 위치들의 수열을 트랙(track)이라 부르며, 트랙의 길이는 연속한 두 기록점 사이의 유클리드 거리를 모두 더한 값으로, 이 값이 배달료 계산의 기준이 된다.

최근 감사에서 일부 트랙이 스스로 교차한다는 사실이 드러났는데, 이는 일부 라이더가 불필요하게 우회했음을 뜻한다. 주어진 트랙에 대해, 첫 번째 기록점에서 마지막 기록점까지 갈 수 있는 가장 짧은 경로의 길이를 구하는 프로그램을 작성하라. 이 경로는 반드시 원래 트랙 위에만 존재해야 하며, 트랙을 따라 원래 방향으로든 반대 방향으로든 이동할 수 있다.

첫째 줄에 처리할 트랙의 개수 $T$가 주어진다.

각 트랙은 트랙을 정의하는 기록점의 개수인 양의 정수 $N$이 적힌 줄로 시작한다. 이어지는 $N$개의 줄에는 각각 공백 하나로 구분된 두 정수가 있으며, 이는 트랙 위 한 점의 $x$좌표와 $y$좌표(단위: 미터)를 나타낸다. 점들은 기록된 순서대로 나열된다.

연속한 두 점은 하나의 선분을 이룬다. 연속한 두 점 사이의 거리는 30미터 이하이며, 각 선분은 다른 선분과 최대 20개까지만 교차한다. 모든 좌표는 -10,000,000 이상 10,000,000 이하의 정수이고, $N$은 $1 \le N \le 100000$을 만족한다.

각 트랙에 대해, 가장 짧은 경로의 길이(미터)를 가장 가까운 정수로 반올림하여 한 줄에 하나씩 출력한다.

양의 실수 $R.xyz$를 가장 가까운 정수로 반올림하는 규칙:

• 소수 첫째 자리 $x$가 5보다 작으면 반올림한 값은 $R$이다.
• 그렇지 않으면 반올림한 값은 $R+1$이다.