시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 256 MB 3 1 1 100.000%

문제

표면 대부분을 사막이 차지하는 미개척 행성에 두 탐사대가 파견되어 개척지를 세웠다. 이 사막은 매우 황량하여 모래 바람이 세차게 불기 때문에 두 개척지는 모두 지하에 건설되었다. 개척지에 출입하기 쉽도록 탐사대는 지면까지 탐사 차량을 운반할 수 있는 수직 리프트를 설치했다. 평소에는 리프트가 올라간 상태로 있다가, 개척지에서 지상으로 올라갈 땐 리프트가 내려오고 차량을 싣고 나서 다시 리프트를 올려보낸다. 반대로 지상에서 개척지로 내려오려면 차량을 리프트에 태운 다음 리프트를 하강시킨다. 

탐사 차량은 앞뒤로 길고, 리프트도 차량 크기에 딱 맞춰 한 쪽은 짧고 다른 쪽은 긴 직사각형 모양이기 때문에 차량을 리프트에 싣는 방법은 두 가지 뿐이다. 예를 들어 리프트의 긴 변이 동서 방향이라면 차량 앞면이 동쪽 또는 서쪽을 향하게 리프트에 실을 수 있다. 이 상태로 지상에 나가면 탐사 차량은 동쪽 또는 서쪽으로 출발할 수 있다. 역으로, 지상에서 임무를 마친 차량이 개척지로 돌아오려면 반드시 동쪽 또는 서쪽을 바라보면서 리프트에 타야 한다. 개척지로 돌아오는 게 아니라면 리프트 위를 어긋난 방향으로 지날 수 있다.

탐사가 진행되는 도중 한 개척지에서 환자가 발생하여 다른 개척지로부터 의약품을 수송받으려 한다. 탐사 차량이 최대한 빨리 의약품을 수송할 수 있도록 최단 경로를 구해주자. 탐사 차량이 좌회전이나 우회전할 때 최소 곡률 반지름은 R이고(즉, 운전대를 왼쪽이나 오른쪽으로 끝까지 꺾으면 차량이 반지름 R인 원을 따라 주행한다), 탐사 차량은 후진할 수 없다. 행성 표면은 2차원 평면으로 가정한다.

입력

첫째 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 100)

테스트케이스의 첫째 줄에는 R이 주어진다. (1 ≤ R ≤ 100)

테스트케이스의 둘째 줄에는 출발하는 개척지의 리프트의 좌표 x1, y1과 리프트의 긴 변이 x축 양의 방향과 반시계 방향으로 이루는 각도 θ1이 주어진다.

테스트케이스의 셋째 줄에는 도착해야 할 개척지의 리프트의 좌표 x2, y2와 리프트의 긴 변이 x축 양의 방향과 반시계 방향으로 이루는 각도 θ2가 주어진다.

(0 ≤ x1, y1x2, y2 ≤ 100; 0 ≤ θ1θ2 < 180)

주어지는 값은 모두 정수이며, 두 리프트는 위치가 같지 않다.

출력

출발 개척지의 리프트에서 도착 개척지의 리프트까지 가는 최단 경로의 길이를 각 테스트케이스마다 한 줄에 하나씩 출력한다. 절대/상대 오차는 10-4까지 허용한다.

예제 입력 1

2
2
0 0 90
0 2 90
10
10 0 0
0 30 90

예제 출력 1

2
35.7079632679

테스트케이스 1: y축 양의 방향을 바라본 상태로 출발 개척지의 리프트에서 나와 그대로 직진하면 도착 개척지의 리프트에 탈 수 있다.

테스트케이스 2: x축 음의 방향을 바라본 상태로 출발 개척지의 리프트에서 나와 반지름 10인 사분원을 따라 우회전하고 직진하면 된다.

예제 입력 2

13
1
0 1 45
1 2 45
100
100 0 135
0 100 135
2
54 70 90
56 74 60
15
15 0 90
0 30 60
7
49 15 60
49 8 120
7
49 15 61
49 8 119
7
49 15 59
49 8 121
32
32 64 0
96 0 0
6
0 0 90
18 0 150
12
10 30 1
9 31 179
50
100 50 20
0 50 20
88
100 50 20
0 50 20
41
2 63 90
84 63 90

예제 출력 2

1.414213562
141.421357727
4.511299166
73.878625387
7.330382858
7.298702080
36.652542301
100.530964915
22.958675460
76.135945854
100.994624329
578.398091882
128.805298797

출처