0 人解决，1 人已尝试。
0 份提交通过，共有 1 份提交。
9.9 EMB 奖励。
2648. Mountain Residence
单点时限: 2.0 sec
内存限制: 256 MB
Imo Company has a piece of land on a rocky mountain and wants to sell it. And a rich person Mr.Uni wants to buy a certain square area of the land with a certain amount of fund and build his house on it. Of course the company hopes that the land will be sold at the highest profit.
Rocks in the rocky mountain are too hard to excavate, so the company has to bury the rocks in soil in order to level the ground. But the company has no skill to find the most suitable square area to be sold at the minimum expense.
The cost to cover the area with soil can be calculated by t − a with the height of the tallest rocks t and the average height of the rocks a in the section for sale of the land that is in proportion to the amount of soil used to bury rocks with.
The cost of the section in the above example is 7/9 because the difference between 3 which is the height of the tallest rock and 2 +2/9 which is the average height of the rocks is 7/9. Additionally 7/9 = 0.77777777 ・ ・ ・ is the lowest cost in any other 3×3 square sections of the land in this example.
输入格式
The input consists of multiple datasets, each in the following format.
n s
a1,1 ・ ・ ・ an,1
…
. . .
…
a1,n ・ ・ ・ an,n
The first line of a dataset contains two positive integers: n (0 < n < 1000), which is the size of the land, and s (0 < s ≤ n), which is the size of the section that Mr. Uni wants to buy. Both the land and the section are regular squares.
Each of the following n line contains n integers separated by single spaces. Each number ai,j (0 ≤ai,j< 1000) shows the height of the rock in the land. The number a1,1, an,1, a1,n and an,n correspond to the north-west corner, the north-east corner, the south-west corner and the south-east corner of the land respectively.
The end of the input is indicated by a line containing two zeroes separated by a space.
输出格式
For each dataset, the minimum cost should be printed. The cost should be in a decimal fraction with an error less than 0.0000001 (= 1.0 × 10-7).
The output must be written to standard output.
样例
Input
5 3 4 1 4 3 1 6 3 2 3 6 0 1 3 1 3 5 3 2 2 2 1 4 6 5 0 3 2 1 2 1 3 1 4 0 4 2 0 0
Output
0.77777778 1.25000000
题目标签