畜栏最小边长问题

题目描述

农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含 $C$ 单位的三叶草，来当做它们的下午茶。

畜栏的边缘必须与 $X$，$Y$ 轴平行。

约翰的土地里一共包含 $N$ 单位的三叶草，每单位三叶草位于一个 $1 \times 1$ 的土地区域内，区域位置由其左下角坐标表示，并且区域左下角的 $X,Y$ 坐标都为整数，范围在 $1$ 到 $10000$ 以内。

多个单位的三叶草可能会位于同一个 $1 \times 1$ 的区域内，因为这个原因，在接下来的输入中，同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中，才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下，能包含至少 $C$ 单位面积三叶草的情况下，畜栏的最小边长是多少。

输入格式

第一行输入两个整数 $C$ 和 $N$。

接下来 $N$ 行，每行输入两个整数 $X$ 和 $Y$，代表三叶草所在的区域的 $X,Y$ 坐标。

同一行数据用空格隔开。

输出格式

输出一个整数，代表畜栏的最小边长。

输入输出样例 #1

输入 #1

3 4
1 2
2 1
4 1
5 2

输出 #1

4

输入输出样例 #2

输入 #2

5 7
1 1
2 2
3 3
4 4
5 5
1 5
5 1

输出 #2

4

限制条件

• $1 \le C \le 500$
• $C \le N \le 500$
• $1 \le X, Y \le 10000$

样例解释 #1

三叶草位置：

1. $(1, 2)$
2. $(2, 1)$
3. $(4, 1)$
4. $(5, 2)$

需要至少包含 $3$ 单位三叶草。

最小正方形边长为 $4$：

• 以 $(1, 1)$ 为左下角，边长为 $4$ 的正方形包含区域：$x \in [1, 5)$, $y \in [1, 5)$
• 包含三叶草：$(1, 2)$, $(2, 1)$, $(4, 1)$ 共 $3$ 单位
• 边长为 $3$ 的正方形无法包含 $3$ 单位三叶草

问题分析

这是一个二维区域覆盖问题：

1. 三叶草坐标是离散的整数点（实际是 $1 \times 1$ 区域）
2. 正方形畜栏的边长是整数，且边缘与坐标轴平行
3. 需要找到最小的边长 $L$，使得存在一个 $L \times L$ 的正方形包含至少 $C$ 单位三叶草
4. 注意：一个 $1 \times 1$ 的区域只有完全在正方形内才被计入

关键点：

• $N \le 500$，可以承受 $O(N^3)$ 的算法
• 坐标范围 $1 \sim 10000$，但只有 $N$ 个点有值
• 可以使用枚举+前缀和的方法

算法思路

1. 离散化所有 $x$ 和 $y$ 坐标
2. 预处理每个离散化后网格的三叶草数量
3. 计算二维前缀和
4. 二分查找边长 $L$，或者从小到大枚举边长 $L$
5. 对于每个边长 $L$，枚举正方形的左下角位置
6. 使用二维前缀和 $O(1)$ 计算正方形内的三叶草总数
7. 如果存在某个正方形包含至少 $C$ 单位三叶草，则该边长可行