시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 462 127 77 23.333%

문제

선영이는 정말 환상적인 지도 앱을 만들고 있다. 지도 앱의 이름은 Moogle Maps이며, Maple mPhone에 탑재될 예정이다. 이 앱은 "Main Street 13"과 같은 도로명 주소의 위치를 가리킬 수 있는 기능이 있다. 하지만, mPhone의 저장 용량은 제한되어 있다. 따라서, 선영이는 데이터의 양을 줄어야 한다.

조금 생각해보니 모든 번지의 위치를 정확하게 저장할 필요는 없다고 생각했다. 그 대신, 일부 번지의 주소만 정확하게 탑재한 다음, 나머지는 선형 보간법 (linearly interpolated)을 이용해서 사용하려고 한다. 이 때, 정확한 집의 위치와 선형 보간법을 사용해 계산한 집의 위치 사이의 오차의 평균값을 최소가 되도록 저장하는 번지의 위치를 선택하려고 한다.

길은 일직선으로 나타낼 수 있고, 첫 번째 집과 마지막 집의 위치는 항상 저장한다.

번지가 i인 집의 위치 xi와 j인 집의 위치 xj를 저장했고, 그 사이의 집은 저장하지 않았을 때, 번지가 k (i < k < j)인 집의 위치를 선형 보간법으로 계산하면 xi + (xj-xi) * (k-i)/(j-i)가 된다.

입력

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

각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 집의 수 h와 저장할 수 있는 집 위치의 수 c가 주어진다. (2 ≤ h ≤ 200, 2 ≤ c ≤ h) 둘째 줄에는 각각의 집의 위치가 주어진다. 위치는 구간 [0, 1000000]에 포함된다. 

출력

각 테스트 케이스에 대해서, h개의 집 중 오차의 평균이 최소가 되도록 c개의 집의 위치를 저장했을 때, 그 오차의 평균을 출력한다. 출력은 소수점 넷째자리까지 하며, 오차는 ±0.001까지 허용한다.

예제 입력

2
4 3
0 9 20 40
10 4
0 10 19 30 40 90 140 190 202 210

예제 출력

0.2500
0.3000

힌트