웜 튜브 우주 여행

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

요약

주어진 3차원 선분을 따라 이동은 무료이며 나머지 이동은 유클리드 거리만큼 비용이 들 때 시작점에서 끝점까지 유료 이동 거리를 최소화합니다.

난이도: 보통10점 중 7점
유형: 최단 경로, 기하, 그래프
정답자: 아직 제출이 없습니다

문제

3차원 공간의 한 점에서 다른 점으로 이동한다. 공간에는 웜 튜브가 놓여 있고, 웜 튜브 하나는 선분이다. 여행자는 웜 튜브 위의 아무 점으로나 들어갈 수 있고 아무 점으로나 나올 수 있으며, 이 이동에는 시간이 전혀 걸리지 않는다. 웜 튜브 밖에서는 이동 시간이 이동 거리에 비례한다.

각 테스트 케이스마다 시작점에서 도착점까지 가는 경로 중 웜 튜브 밖에서 이동한 거리의 최솟값을 구한다.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스의 첫째 줄에는 웜 튜브의 개수 $N$ 이 주어진다. 다음 줄에는 경로의 시작점을 나타내는 정수 $sx$ , $sy$ , $sz$ 가 주어지고, 그 다음 줄에는 도착점을 나타내는 정수 $ex$ , $ey$ , $ez$ 가 주어진다.

이어서 $N$ 개의 줄이 주어진다. $i$ 번째 줄에는 정수 여섯 개 $sx_i$ , $sy_i$ , $sz_i$ , $ex_i$ , $ey_i$ , $ez_i$ 가 주어지며, 이는 $i$ 번째 웜 튜브의 두 끝점이다.

$0 < T \le 50$
$0 \le N \le 50$
모든 좌표는 $0 < c \le 1000$ 인 정수다.
한 웜 튜브의 두 끝점은 서로 다르다.
시작점과 도착점이 같을 수 있다.

출력

각 테스트 케이스마다 웜 튜브 밖에서 이동한 거리의 최솟값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 하나씩, 입력 순서대로 출력한다.

예제2

예제 1

입력

2
0
10 12 15
9 11 16
2
100 100 100
123 126 129
102 109 103 110 120 113
108 121 104 120 125 122

예상 출력

1.732051
21.567207

예제 2
입력
```
1
1
1 1 1
10 1 1
1 1 1 10 1 1
```
예상 출력
```
0.000000
```