#P6869. 子矩形

    ID: 6700 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索暴力枚举排序与序列处理一维前缀和计算几何凸包单调栈叉积二分查找数值计算与优化有理数精确运算CF2300

子矩形

子矩形

题目描述

给定一个 n×nn\times n 的整数矩阵 AA,Ai,jA_{i,j} 表示第 ii 行第 jj 列的数。

选择非空子矩形,左上角为 (x1,y1)(x_1,y_1),右下角为 (x2,y2)(x_2,y_2),其中 1≤x1≤x2≤n1\le x_1\le x_2\le n,1≤y1≤y2≤n1\le y_1\le y_2\le n。

定义其周长为

P=2(x2−x1+1)+2(y2−y1+1),P=2(x_2-x_1+1)+2(y_2-y_1+1),

定义其“面积”为格子数值之和

S=∑i=x1x2∑j=y1y2Ai,j.S=\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}A_{i,j}.

求使 S/PS/P 最大的子矩形,输出最大比值和一种对应的子矩形。这里 xx 表示行号,yy 表示列号;数值之和可以为负。

输入格式

第一行一个正整数 nn。

接下来 nn 行,每行 nn 个整数,描述矩阵 AA。

输出格式

第一行一个浮点数,表示最大比值。

第二行两个整数 x1,y1x_1,y_1,第三行两个整数 x2,y2x_2,y_2,表示所选子矩形。

输出的比值与正确答案之间,以及所选子矩形的实际比值与输出比值之间,绝对误差或相对误差不超过 10−710^{-7} 均可接受。对正确值 bb 与输出值 aa,这等价于

∣a−b∣≤10−7max⁡(1,∣b∣).|a-b|\le10^{-7}\max(1,|b|).

样例输入

2
100 100
1 1

样例输出

33.33333333333
1 1
1 2

样例解释

选择第一行的两个格子,S=200S=200、P=6P=6,比值为 100/3100/3。

其他样例

见原题下发文件 rectangle2.in/out 与 rectangle3.in/out。

数据范围

1≤n≤5001\le n\le500,∣Ai,j∣≤109|A_{i,j}|\le10^9。

  • 子任务 11(10%10\%):n≤100n\le100。
  • 子任务 22(30%30\%):n≤300n\le300。
  • 子任务 33(60%60\%):无额外限制。