本题没有可用的提交语言。

题目描述

考虑一个由 $M$ 行和 $N$ 列组成的平面网格。该网格共有 $M \times N$ 个交叉点，每个交叉点的坐标表示为 $(i, j)$，其中 $i = 0, 1, \dots, N-1$，$j = 0, 1, \dots, M-1$。

假设现在有 $K \leq M \times N$ 个点被放置在 $K$ 个不同的网格交叉点上。

定义一个菱形区域 $D(i, j, r)$，其中心位于交叉点 $(i, j)$，形状为对角线长度为 $2r$ 的正方形，并顺时针旋转 45 度，其中 $i = 0, 1, \dots, N-1$，$j = 0, 1, \dots, M-1$，$r$ 为菱形的半径，可以是任意正整数。

Manoranjan 感兴趣的是找到菱形的最小半径 $R_{\text{min}}(P_{\text{min}})$，使得无论菱形的中心位于网格的哪个交叉点，该菱形都至少覆盖 $P_{\text{min}}$ 个点，其中 $P_{\text{min}} = 1, 2, \dots, K$。同时，设 $P_{\text{max}}(P_{\text{min}})$ 为半径 $R_{\text{min}}(P_{\text{min}})$ 的菱形最多能覆盖的点数。考虑以下示例：五个点 $(0,0)$、$(4,0)$、$(2,2)$、$(0,4)$ 和 $(4,4)$ 被放置在 $5$ 行 $7$ 列的网格上。菱形 $D(2,4,1)$ 不覆盖任何点，$D(2,1,2)$ 覆盖 $1$ 个点，$D(3,3,4)$ 覆盖 $4$ 个点。

输入格式

第 $1$ 行给出网格的行数 $M$ 和列数 $N$。接下来的若干行给出 $K$ 个点的坐标 $(x, y)$，其中 $K \leq M \times N$。可以假设 $1 \leq M \leq 100$，$1 \leq N \leq 100$。每个点的坐标由两个整数表示，分别对应 $x$ 和 $y$ 坐标。输入中的所有数值由一个或多个空白字符（包括空格和制表符）分隔。超出网格范围的点将被视为无效输入并丢弃（例如，样例输入中的最后一个点 $(0,5)$ 会被丢弃）。

输出格式

对于每一个可能的 $P_{\text{min}}$ 值，输出一行，格式为：

Pmin Rmin(Pmin) Pmax(Pmin)

仅当 $R_{\text{min}}(P_{\text{min}})$ 保证恰好覆盖 $P_{\text{min}}$ 个点时，才输出该行。例如，在样例输出中，没有 $P_{\text{min}}=2$ 的行，因为 $R_{\text{min}}(2) = R_{\text{min}}(3) = 6$。

所有数值应右对齐列标题。

输入样例 1

5 	7
0 	0 0 	4
4 0
4 4	       2 2
	0 5

输出样例 1

Pmin Rmin(Pmin) Pmax(Pmin)
   1           4           5
   3           6           5
   4           8           5
   5          10           5

来源

达卡 2002