#P2020094. 星际旅行
星际旅行
星际旅行
题目描述
在一个n维欧几里得空间的宇宙中,小 A 打算完成一次星际旅行。
利用n维直角坐标系,宇宙中每个点的位置都可以用n维坐标来表示。其中,在宇宙中心的O点(未必是坐标系原点)处,有一个半径为r的超球体黑洞,任何物体若落入黑洞内部(不包括其表面)则无法逃脱。
小 A 选定了m个不在黑洞内部的点P1,P2,⋯,Pm,作为他星际旅行的目标。不会有两个点处于同一位置。
为了提前做好旅行规划,小 A 希望求出这m个点两两之间的最短曲线距离。同样地,这些曲线不能经过黑洞的内部。为了方便,你只需要输出每个点到其他m−1个点的距离之和。
输入格式
第一行两个整数n,m。
第二行一个整数r。
第三行n个整数,依次表示超球体黑洞的中心O的每一维坐标。
接下来m行,每行n个整数。第i行的各个整数依次表示点Pi的每一维坐标。
同一行内的多个整数之间用一个空格隔开。
输出格式
输出一共m行,每行一个实数。第i行表示第i个点(Pi)到其他所有点的最短曲线距离之和。
请以“整数部分、小数点、小数部分”的格式输出实数,并保留不少于 12 位小数结果。采用其他格式(如科学记数法)输出可能无法得分。
数据范围
(原站未提供,导入后需人工补齐)
样例
2 3
2
3 1
5 1
1 3
3 -2
8.83711594354348
10.83711594354348
9.39104657990738
3 8
1
0 0 0
0 0 1
0 1 0
1 0 0
1 1 1
-1 -1 0
-1 0 -1
0 -1 -1
-1 -1 -1
14.12797001266400
14.12797001266400
14.12797001266400
17.90086240651788
13.95502966750398
13.95502966750398
13.95502966750398
14.99490548122857
提示
样例1说明
如下图所示,圆O为二维平面上的黑洞,P1,P2,P3为小 A 星际旅行的目标。

通过在圆周上选择合适的点A,B,C,D,可以证明,
曲线P1AP2,P2BCP3,P3DP1分别为这三对点之间满足条件的最短曲线。
这些曲线的长度分别为 5.14159265358979, 5.69552328995369, 3.69552328995369。
评分方法
对于每个测试点,你的结果正确则得该测试点的满分,错误不得分。你的输出被认为是正确的,当且仅当你输出的每个实数与对应答案的相对或绝对误差不超过10−9。
为了达到这一精度要求,请不要使用单精度浮点数(对应 C、C++、Java 语言的float类型,机器精度约10−6级别)完成本题,而应当使用双精度浮点数(对应 C、C++、Java 语言的double类型、Python 语言的float类型,机器精度约10−15级别)或更精确的表示法(如整数类型int,前提是不能超出该类型的表示范围)。
评测用例规模与约定
本题共 20 个测试点,每个 5 分。
对于所有的测试点,2≤n≤100,2≤m≤2000,1≤r≤1000.

输入中的所有坐标均在[−1000,1000]范围内。