子矩形
题目描述
给定一个 n×n 的整数矩阵 A,Ai,j 表示第 i 行第 j 列的数。
选择非空子矩形,左上角为 (x1,y1),右下角为 (x2,y2),其中 1≤x1≤x2≤n,1≤y1≤y2≤n。
定义其周长为
P=2(x2−x1+1)+2(y2−y1+1),
定义其“面积”为格子数值之和
S=i=x1∑x2j=y1∑y2Ai,j.
求使 S/P 最大的子矩形,输出最大比值和一种对应的子矩形。这里 x 表示行号,y 表示列号;数值之和可以为负。
输入格式
第一行一个正整数 n。
接下来 n 行,每行 n 个整数,描述矩阵 A。
输出格式
第一行一个浮点数,表示最大比值。
第二行两个整数 x1,y1,第三行两个整数 x2,y2,表示所选子矩形。
输出的比值与正确答案之间,以及所选子矩形的实际比值与输出比值之间,绝对误差或相对误差不超过 10−7 均可接受。对正确值 b 与输出值 a,这等价于
∣a−b∣≤10−7max(1,∣b∣).
样例输入
2
100 100
1 1
样例输出
33.33333333333
1 1
1 2
样例解释
选择第一行的两个格子,S=200、P=6,比值为 100/3。
其他样例
见原题下发文件 rectangle2.in/out 与 rectangle3.in/out。
数据范围
1≤n≤500,∣Ai,j∣≤109。
- 子任务 1(10%):n≤100。
- 子任务 2(30%):n≤300。
- 子任务 3(60%):无额外限制。