二分法 + 离散化 + 二维前缀和 + 扫描线

时间复杂度

O(N^2*log(R))
其中N表示三叶草的个数, R表示max(X坐标的极差, Y坐标的极差)
N <= 500, R <= 10000

Python 代码

from bisect import bisect_left

def get(i, j):
    if i < 0 or j < 0:
        return 0
    else:
        return presum[i][j]

def check(side):
    # 时间复杂度为O(N^2)
    # 二重循环逆序遍历畜栏的右上角坐标(x_max, y_max)
    # 之所以是逆序的, 因为左上角坐标更不容易越界, 得到完整的side * side畜栏, 能够更快速找到三叶草个数大于等于C的畜栏.
    # 找到一个, 即可返回True, 找不到, 返回False

    D = {}
    for i in range(len(Xs) - 1, -1, -1):
        x_max = Xs[i] + 1 # +1是因为必须包含整个小方块, 相当于要包含小方块的右上角
        x_min = x_max - side # (x_min, y_min)为畜栏的左下角坐标
        i2 = bisect_left(Xs, x_min) - 1
        for j in range(len(Ys) - 1, -1, -1):
            if presum[i][j] < C: break
            y_max = Ys[j] + 1 # +1是因为必须包含整个小方块, 相当于要包含小方块的右上角
            y_min = y_max - side
            if j not in D:
                j2 = bisect_left(Ys, y_min) - 1
                D[j] = j2
            else:
                j2 = D[j]
            cnt = get(i, j) - get(i2, j) - get(i, j2) + get(i2, j2) # 二维差分, O(1)求出畜栏中的三叶草的个数
            if cnt >= C: return True
    return False



C, N = map(int, input().split())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

# 离散化X, Y坐标, 目的是减少时间复杂度与空间复杂度
Xs = [0] + sorted(set(X))
Ys = [0] + sorted(set(Y))

# 二维前缀和presum
presum = [[0] * len(Ys) for _ in range(len(Xs))]
for i in range(N):
    r = bisect_left(Xs, X[i])
    c = bisect_left(Ys, Y[i])
    presum[r][c] += 1

for i in range(1, len(Xs)):
    for j in range(1, len(Ys)):
        presum[i][j] += presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1]
#print(presum)

# 二分法搜索满足条件的最小畜栏边长
l, r = 1, max(max(Xs) - min(Xs) + 1, max(Ys) - min(Ys) + 1)
while l < r:
    mid = (l + r) >> 1
    if check(mid):
        r = mid
    else:
        l = mid + 1
print(l)