
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 subrectangle as the new choir. Cici doesn't know how to choose the subrectangle 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 subrectangle of a*b? InputThe 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. OutputFor 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 lefttop 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 multirectangle with the same variance, choose the point with smaller sx (when sx is equal, choose sy smaller first). Variance: http://en.wikipedia.org/wiki/Variance Sample Input4 5 180 210 198 156 200 199 123 178 210 202 133 145 159 150 130 123 178 165 199 210 1 2 2 Sample OutputCase 1: (3, 3), 38.00 Author: LI, Fei Contest: ZOJ Monthly, June 2012 