ZOJ Problem Set - 3614
Cici is a member of the school choir. In order to celebrate the 90th birthday of communist party of China, Cici plans to choose some of her firends to form a new choir. Choosing is a difficult problem when Cici want to get a perfect choir. Here, a perfect choir means the variance of the poeple's height except the tallest one is the smallest. (the tallest one will be the leader singer, so you don't need to count his height when calculating the variance)
Here, in order to simplify the problem, we assume that everyone is standing on a fixed position, that is we have m*n people standing on a m*n (0 < m, n < 300) rectangle. And Cici wants to choose a sub-rectangle as the new choir. Cici doesn't know how to choose the sub-rectangle from this m*n rectangle. So, as a programmer, can you help her to get the smallest variance on the people Cici choose when Cici gives you a sub-rectangle of a*b?
The input file consists of several test cases. The first line of each test case contains two integers m, n (0 < m, n < 300), indicating the rectangle of the people.
Then following m lines, each line has n numbers indicate the height of each person (each number is an integer between 120 and 220).
The next line contains a number q (0 < q <= 100) indicate the queries Cici asks you.
Then following q lines, each line contains two numbers a, b (1 < a <= m, 1 < b <= n, ) indicate that Cici want to get a a * b rectangle with the smallest variance.
For each test case, print q + 1 lines.
The first line contains the case number (they are numbered sequentially starting from 1)
Then following q lines, each line print the left-top position you choose and the variance in the format "(sx, sy), variance" (the variance is rounded to two digits after decimal point).
Note: For each query, if there are multi-rectangle with the same variance, choose the point with smaller sx (when sx is equal, choose sy smaller first).
4 5 180 210 198 156 200 199 123 178 210 202 133 145 159 150 130 123 178 165 199 210 1 2 2
Case 1: (3, 3), 38.00
Author: LI, Fei
Contest: ZOJ Monthly, June 2012