시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 537 164 96 25.131%

문제

선영이는 정말 환상적인 지도 앱을 만들고 있다. 지도 앱의 이름은 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까지 허용한다.

예제 입력 1

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

예제 출력 1

0.2500
0.3000
W3sicHJvYmxlbV9pZCI6IjUwNjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWFlMDAgXHViOWY1XHVjMmE0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjODE1XHViOWQwIFx1ZDY1OFx1YzBjMVx1YzgwMVx1Yzc3OCBcdWM5YzBcdWIzYzQgXHVjNTcxXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzljMFx1YjNjNCBcdWM1NzFcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIE1vb2dsZSBNYXBzXHVjNzc0XHViYTcwLCBNYXBsZSBtUGhvbmVcdWM1ZDAgXHVkMGQxXHVjN2FjXHViNDIwIFx1YzYwOFx1YzgxNVx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YzU3MVx1Yzc0MCAmcXVvdDtNYWluIFN0cmVldCAxMyZxdW90O1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViM2M0XHViODVjXHViYTg1IFx1YzhmY1x1YzE4Y1x1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVhYzAwXHViOWFjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhZTMwXHViMmE1XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBtUGhvbmVcdWM3NTggXHVjODAwXHVjN2E1IFx1YzZhOVx1YjdjOVx1Yzc0MCBcdWM4MWNcdWQ1NWNcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVjNTkxXHVjNzQ0IFx1YzkwNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg3MFx1YWUwOCBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWIyYzggXHViYWE4XHViNGUwIFx1YmM4OFx1YzljMFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1YzgwMFx1YzdhNVx1ZDU2MCBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0XHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YjJlNC4gXHVhZGY4IFx1YjMwMFx1YzJlMCwgXHVjNzdjXHViZDgwIFx1YmM4OFx1YzljMFx1Yzc1OCBcdWM4ZmNcdWMxOGNcdWI5Y2MgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1ZDBkMVx1YzdhY1x1ZDU1YyBcdWIyZTRcdWM3NGMsIFx1YjA5OFx1YmEzOFx1YzljMFx1YjI5NCBcdWMxMjBcdWQ2MTUgXHViY2Y0XHVhYzA0XHViYzk1IChsaW5lYXJseSBpbnRlcnBvbGF0ZWQpXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzgxNVx1ZDY1NVx1ZDU1YyBcdWM5ZDFcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YzEyMFx1ZDYxNSBcdWJjZjRcdWFjMDRcdWJjOTVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTc0IFx1YWNjNFx1YzBiMFx1ZDU1YyBcdWM5ZDFcdWM3NTggXHVjNzA0XHVjZTU4IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM2MjRcdWNjMjhcdWM3NTggXHVkM2M5XHVhZGUwXHVhYzEyXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVjODAwXHVjN2E1XHVkNTU4XHViMjk0IFx1YmM4OFx1YzljMFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTM4XHVjNzQwIFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5ZDFcdWFjZmMgXHViOWM4XHVjOWMwXHViOWM5IFx1YzlkMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzg4XHVjOWMwXHVhYzAwIGlcdWM3NzggXHVjOWQxXHVjNzU4IFx1YzcwNFx1Y2U1OCB4PHN1Yj5pPFwvc3ViPlx1YzY0MCBqXHVjNzc4IFx1YzlkMVx1Yzc1OCBcdWM3MDRcdWNlNTggeDxzdWI+ajxcL3N1Yj5cdWI5N2MgXHVjODAwXHVjN2E1XHVkNTg4XHVhY2UwLCBcdWFkZjggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc0MCBcdWM4MDBcdWM3YTVcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTU4XHVjNzQ0IFx1YjU0YywgXHViYzg4XHVjOWMwXHVhYzAwIGsgKGkgJmx0OyBrICZsdDsgailcdWM3NzggXHVjOWQxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWMxMjBcdWQ2MTUgXHViY2Y0XHVhYzA0XHViYzk1XHVjNzNjXHViODVjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YmE3NCB4PHN1Yj5pPFwvc3ViPiArICh4PHN1Yj5qPFwvc3ViPi14PHN1Yj5pPFwvc3ViPikgKiAoay1pKVwvKGotaSlcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCB0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB0ICZsZTsgNTApPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5ZDFcdWM3NTggXHVjMjE4IGhcdWM2NDAgXHVjODAwXHVjN2E1XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOWQxIFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWMyMTggY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgaCAmbGU7IDIwMCwgMiAmbGU7IGMgJmxlOyBoKSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM5ZDFcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzA0XHVjZTU4XHViMjk0IFx1YWQ2Y1x1YWMwNCBbMCwgMTAwMDAwMF1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgaFx1YWMxY1x1Yzc1OCBcdWM5ZDEgXHVjOTExIFx1YzYyNFx1Y2MyOFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBjXHVhYzFjXHVjNzU4IFx1YzlkMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YzYyNFx1Y2MyOFx1Yzc1OCBcdWQzYzlcdWFkZTBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWM3NDAgXHVjMThjXHVjMjE4XHVjODEwIFx1YjEzN1x1YzlmOFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWQ1NThcdWJhNzAsIFx1YzYyNFx1Y2MyOFx1YjI5NCAmcGx1c21uOzAuMDAxXHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1MDYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTW9vZ2xlIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgZ290IHRoZSBvcmlnaW5hbCBpZGVhIG9mIG1ha2luZyBtYXAgc29mdHdhcmUsIGNhbGxlZCBNb29nbGUgTWFwcywgZm9yIHRoZSBuZXcgY29vbCBNYXBsZSBtUGhvbmUuIEl0IHdpbGwgZXZlbiBiZSBjYXBhYmxlIG9mIGluZGljYXRpbmcgdGhlIGxvY2F0aW9uIG9mIGEgaG91c2UgYWRkcmVzcyBsaWtlICZyZHF1bztNYWluIFN0cmVldCAxMyZyZHF1bzsuIEhvd2V2ZXIsIHNpbmNlIHRoZSBtUGhvbmUgaGFzIGxpbWl0ZWQgc3RvcmFnZSBjYXBhY2l0eSwgeW91IG5lZWQgdG8gcmVkdWNlIHRoZSBkYXRhIGFtb3VudC4gWW91IGRvbiZyc3F1bzt0IHdhbnQgdG8gc3RvcmUgdGhlIGV4YWN0IGxvY2F0aW9uIG9mIGV2ZXJ5IHNpbmdsZSBob3VzZSBudW1iZXIuIEluc3RlYWQgb25seSBhIHN1YnNldCBvZiB0aGUgaG91c2UgbnVtYmVycyB3aWxsIGJlIHN0b3JlZCBleGFjdGx5LCBhbmQgdGhlIG90aGVycyB3aWxsIGJlIGxpbmVhcmx5IGludGVycG9sYXRlZC4gU28geW91IHdhbnQgdG8gc2VsZWN0IGhvdXNlIG51bWJlcnMgdGhhdCB3aWxsIG1pbmltaXNlIHRoZSBhdmVyYWdlIGludGVycG9sYXRpb24gZXJyb3IsIGdpdmVuIGhvdyBtYW55IGhvdXNlIGxvY2F0aW9ucyB5b3UgaGF2ZSBjYXBhY2l0eSB0byBzdG9yZS4gV2UgdmlldyB0aGUgc3RyZWV0IGFzIGEgc3RyYWlnaHQgbGluZSwgYW5kIHlvdSB3aWxsIGFsd2F5cyBzdG9yZSB0aGUgXHVmYjAxcnN0IGFuZCB0aGUgbGFzdCBob3VzZSBsb2NhdGlvbi48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhhdCB5b3UmcnNxdW87dmUgc3RvcmVkIHRoZSBsb2NhdGlvbnMgeDxzdWI+aTxcL3N1Yj4gYW5kIHg8c3ViPmo8XC9zdWI+IGZvciB0aGUgaG91c2VzIHdpdGggbnVtYmVycyBpIGFuZCBqIHJlc3BlY3RpdmVseSwgYnV0IG5vIG90aGVyIGhvdXNlIGluIGJldHdlZW4sIHRoZSBpbnRlcnBvbGF0ZWQgdmFsdWUgZm9yIGEgaG91c2Ugd2l0aCBudW1iZXIgayB3aXRoIGkgJmx0OyBrICZsdDsgaiBpcyZuYnNwO3g8c3ViPmk8XC9zdWI+Jm5ic3A7KyAoeDxzdWI+ajxcL3N1Yj4teDxzdWI+aTxcL3N1Yj4pICogKGstaSlcLyhqLWkpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgZ2l2ZXMgYSBzaW5nbGUgaW50ZWdlciwgMSAmbGU7IHQgJmxlOyA1MCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLjxcL3A+XHJcblxyXG48cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZXJlIGFyZSB0d28gbGluZXMuIFRoZSBmaXJzdCBjb250YWlucyAyICZsZTsgaCAmbGU7IDIwMCBhbmQgMiAmbGU7IGMgJmxlOyBoLCB3aGVyZSBoIGlzIHRoZSBudW1iZXIgb2YgaG91c2VzIGluIHRoZSBzdHJlZXQgYW5kIGMgaXMgdGhlIG51bWJlciBvZiBob3VzZSBsb2NhdGlvbnMgdGhhdCBjYW4gYmUgc3RvcmVkLiBUaGUgc2Vjb25kIGNvbnRhaW5zIGggaW50ZWdlcnMgaW4gaW5jcmVhc2luZyBvcmRlciBnaXZpbmcgdGhlIGxvY2F0aW9uIG9mIHRoZSBoIGhvdXNlcy4gRWFjaCBsb2NhdGlvbiBpcyBpbiB0aGUgaW50ZXJ2YWwgWzAsIDEwMDAwMDBdLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSBhdmVyYWdlIGludGVycG9sYXRpb24gZXJyb3Igb3ZlciBhbGwgdGhlIGggaG91c2VzIGZvciB0aGUgb3B0aW1hbCBzZWxlY3Rpb24gb2YgYyBob3VzZSBsb2NhdGlvbnMgdG8gc3RvcmUuIFRoZSBvdXRwdXQgc2hvdWxkIGJlIGdpdmVuIHdpdGggZm91ciBkZWNpbWFsIHBsYWNlcywgYnV0IHdlIHdpbGwgYWNjZXB0IGluYWNjdXJhY2llcyBvZiB1cCB0byAmcGx1c21uOzAuMDAxLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==