레이팅 미적용상업 비행은 통계적으로 꽤 안전하다(passeng\(er-ki\)lometer, 즉 승객·킬로미터당 사망자 수 기준으로는 달에 가는 것만이 더 안전하다). 그래도 예방 조치와 안전 규정이 필요한 이유는 있다. 초기의 그런 규칙 중 하나가 이른바(\(so-ca\)lled) “60분(\(60-mi\)nute) 규칙”으로, 쌍발(t\(wo-en\)gine) 비행기는 전체 비행 경로 내내 가장 가까운 적절한 공항에서 60분 이내에 있어야 한다는 것이었다. 비슷한 규칙이 여럿 있었지만 핵심은 같다. 비행 경로는 비행기를 가장 가까운 공항으로부터 정해진 최대 허용 거리보다 멀리 데려갈 수 없다. 이런 제한 때문에 비행기는 한 공항에서 다른 공항으로 갈 때 항상 직항 경로를 쓸 수는 없다. 이 문제에서는 최대 허용 거리(m\(ax- im\)um allowed distance) 규칙을 지키면서 두 공항 사이의 최단 비행 경로를 계산한다. 첫 번째 샘플 테스트 케이스를 나타낸 아래 그림에서, 모든 비행 경로는 세 원 안에 있어야 한다. 따라서 공항 2에서 공항 3으로 가는 비행기는 공항 1 주변 지역을 경유해 직항 경로에서 우회해야 한다. 비행기가 반드시 공항 1 자체에 갈 필요는 없다는 점에 유의하라. 비행기의 연료 공급이 제한되어 있어 더 먼 거리를 가려면 중간 공항에 기착해야 할 수도 있다는 사실이 문제를 더 복잡하게 만든다. 따라서 연료 용량에 따라, 그림에서 공항 2에서 공항 3으로 가는 비행기는 공항 1에 기착해야 할 수도 있다(또는 연료 용량이 너무 작아 공항 1까지도 갈 수 없어 여행이 불가능할 수도 있다). 다음과 같은 단순화 가정을 둔다. 1. 지구 표면은 반지름 6370 km의 구이다. 2. 시간과 연료 소비는 모두 이동 거리에 정비례한다. 즉, 총 이동 거리에만 관심이 있다. 3. 비행기가 서로 다른 고도로 나는 데서 오는 거리 차이는 무시할 수 있다. 따라서 사실상(eff\(ec- ti\)vely) 비행기가 지구 표면을 따라 난다고 가정한다. 4. 비행기는 필요한 만큼 여러 중간 공항에 기착해 재급유할 수 있으며, 그때마다 연료를 가득 채운다.
각 테스트 케이스의 첫 줄에는 두 정수 \(N\)과 \(R\)이 주어진다. \(2 \le N \le 25\)는 공항의 수이고 \(1 \le R \le 10\,000\)은 가장 가까운 공항으로부터의 최대 허용 비행 거리(km)이다. 다음 \(N\)개의 줄에는 각각 0 ≤φ < 360 a\(nd - 90\) ≤θ ≤90을 만족하는 두 정수 φ, θ가 주어지며, 이는 각각 공항의 경도와 위도(도 단위)이다. 공항은 입력에 나온 순서대로 1부터 번호가 매겨진다. 같은 위치에 있는 두 공항은 없다. 이어서 \(1 \le Q \le 100\)을 만족하는 정수 \(Q\)가 있는 줄이 주어진다. 다음 \(Q\)개의 줄에는 각각 \(1 \le s\), \(t \le N\), \(s\)̸ = \(t\), \(1 \le c \le 50\,000\)을 만족하는 세 정수 \(s\), \(t\), \(c\)가 주어지며, 이는 연료 용량으로 \(c\) km의 항속 거리를 갖는 비행기가 공항 \(s\)에서 공항 \(t\)로 감을 나타낸다.
각 테스트 케이스마다 케이스 번호와 함께, 질의마다 연료 제약 \(c\)를 지키면서 공항 \(s\)에서 \(t\)까지 가는 최단 비행 경로의 길이(km)를 한 줄씩 출력한다. 길이는 소수점 아래 셋째 자리까지 정확하게 출력한다. 두 공항 사이에 허용되는 경로가 없으면 대신 impossible을 출력한다. 답은 \(R\) 또는 \(c\)를 0.1 km까지 흔들어도 수치적으로 안정적이라고 가정해도 된다.
3 2000
0 0
0 30
30 0
3
2 3 5000
2 3 4000
2 3 3000
2 10000
45 45
225 -45
2
1 2 50000
2 1 50000
Case 1:
4724.686
6670.648
impossible
Case 2:
impossible
impossible