商业航班在统计学意义上很安全（考虑到死亡人数/(乘客*公里数)，只有去月球比商业航班更安全），但是安全规定和事故预防仍然是有其原因的。一条较早的规定是所谓的“60分钟原则”，要求双引擎飞机在飞行全程中任何时刻离最近的机场距离不得超过60分钟路程。还有许多类似的原则，但他们在核心问题上是一致的：**在航线上任何一点，飞机与最近的机场的距离不得超过一个给定值**。在这些规定的限制下，飞机在两机场间飞行时不一定能直达。在这道题目中，我们将计算考虑了“最远距离规定”情况下两机场之间的最短飞行路程。下图描述了一个样例：任何航线都不能超出三个圆的并集，因此从2机场飞往3机场的飞机必须绕行1机场附近的空域。注意：飞机本身不一定要降落在1机场。 ![原题图](https://cdn.luogu.org/upload/pic/61797.png ) 飞行过程还受到飞机的燃料容量限制：如果要长距离飞行，飞机还可能在某些机场中转加油。因此由于燃料容量的限制，从2飞往3的飞机可能需要在1机场中转（也存在一种可能即飞机的燃料甚至不足以使其从2飞往1，那么该航班无法开通）。 ------------ 我们做出如下简化的假设： **①地球表面是一个半径6370km的球面。** **②时间和燃料的消耗与飞行路程成正比，换言之，我们只关心总飞行路程。** **③不考虑飞行高度对距离的影响，因此你可以认为飞机在贴地飞行。** **④飞机可以在途中无限次中转加油，每次中转后油箱都会加满。** ------------ 输入：第一行输入包含两个正整数N和R，N代表机场数目(2<=N<=25)，R表示与最近机场的距离的最大值(1<=R<=10000,单位为km)。以下N行每行有两个整数Φ和θ，分别表示机场经纬度(0<=Φ<360, -90<=θ<=90,单位均为度)。机场按照输入顺序编号，两机场不会出现在在同一位置。下一行输入为整数Q(1<=Q<=100)。接下来Q行每行包含三个整数s, t, c，表示一架飞机从s飞往t，燃料容量限制为c(1<=s, t <=N, s≠t, 1<=c<=50000,c的单位为km)。输出：对每个测试点，输出测试点序号和该测试点所求的s和t机场间的受到燃油容量c限制下的最短飞行距离，保留三位小数。如果航班无法开通，则输出"impossible"。 R和c保留至小数点后一位即可满足精度要求。样例输入： 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

UVA1288 最短飞行路径 Shortest Flight Path

Description

Input Format

Output Format