考虑容斥，枚举一个点集，算包含这个点集的方案。直接容斥的复杂度是 $O(2^k)$，但是注意包含点集的最小矩形的端点只有 $O(k)$ 个，所以总共只有 $O(k^4)$ 个矩形。

进一步的，如果一个矩形严格内部有点，那么它的容斥系数是 $0$（内部的点可选可不选）。不妨设所有点的横纵坐标互不相同（相等的可以钦定一个顺序，不改变答案），那么枚举左右端点，有贡献的矩形至多只有 $4$ 个。所以总共只有 $O(k^2)$ 个这样的矩形。对每个矩形，枚举边长 $d$，贡献是一个分段四次多项式，可以分段插值。

总时间复杂度 $O(k^2)$。