1218 - Acman and his GirlFriend

Time Limit: 5s Memory Limit: 128MB

Submissions: 98 Solved: 29
Description
ACman has been studying in HUST for nearly four years, and he thinks Wuhan is a very beautiful city even though he doesn’t like the weird weather. One day, he invited his girl friend Brandy to go shopping, they found that there were many shopping malls in the city center. Brandy had no idea which mall should they enter, because they had only limited time for shopping. She asked ACman for a help. ACman loved Maths as much as Brandy, he considered the beauty in Maths as the most beauty in the world. There were N(1 <= N <= 100000) shopping malls lying on a line, and the distance between the adjacent malls was one meter. Every malls has his own height, and different malls might be the same height. You could select n continuous malls on condition that n must be M(1<=M<=N) at least for some reason, and the beautiful value was defined as the ratio of the sum of the n malls’ heights and the number of the continuous selected malls, namely, n. What was the most beautiful value? As a good programmer, Could you help ACman solve the problem? If you can solve it correctly, ACman will give you a beautiful balloon.
Input
The first line of input is an integer giving number of cases to follow. For each case: The first line contains two integers N, M separated by a single space. The second line contains N integers which represent the heights of the N shopping malls on a line from left to right. The heights of shopping malls are positive integers and less than 100000.
Output
Print a single integer which is the most beautiful value rounded to three digits after the decimal point.
Sample Input
1
5 2
1 3 2 7 1
Sample Output
4.500
Hint
Source
ACman, HUST Programming Contest 2007