1462 - 第二届“华为杯”初赛题目G

Time Limit : 3 Second

Memory Limit : 128 MB

Submission: 22

Solved: 11

Description


在数轴上有n个点x1xn,你需要选择m个点,其中第一个点和最后一个点必选,以这m个点为依据,对其余点进行线性插值。你希望使得插值的误差尽可能小。如果选择了xi,xj,那么对于 i < k < j ,插值结果为xi+(xj-xi)*(k-i)/(j-i),误差为|xk -xi+(xj-xi)*(k-i)/(j-i)|。 


Input


第一行有一个正整数 t ,表示数据组数(不多于50)。每组数据第一行有两个整数, nm,满足2 ≤ n ≤ 200 and 2 ≤ m≤ n。其中n是点的总数,m是需要选择的点的个数。第二行有n个按照增序排列的数字,表示n个的位置,每一个都在范围[0, 1000000]内。


Output


每一个测试数据都只需输出对应的最小误差,输出精确到小数点后4位。


sample input
2
4 3
0 9 20 40
10 4
0 10 19 30 40 90 140 190 202 210
sample output
0.2500
0.3000
hint
source
© 2015 HUST ACMICPC TEAM. All Right Reserved.