题目大意

给定一个 $(N+1) \times (M+1)$ 的网格点图，其中有 $K$ 个点被删除。需要计算在剩下的格点中，能够形成多少个正方形（正方形的四个顶点都必须是未被删除的格点）。

解题思路

问题分析

这个问题需要统计所有可能的正方形，包括：

• 边与坐标轴平行的正方形
• 边倾斜的正方形（顶点仍在格点上）

由于 $N$ 和 $M$ 可能很大（最大 $10^6$），而 $K$ 相对较小，我们需要一种高效的计数方法。

核心思想：容斥原理

本题采用容斥原理来避免重复计数和漏计：

1. 计算所有可能的正方形总数（不考虑点被删除）

   • 对于边长为 $i$ 的轴对齐正方形，有 $(N-i+1) \times (M-i+1)$ 个
   • 对于倾斜的正方形，需要通过几何关系进行计数

2. 减去包含被删除点的正方形

   • 对于每个被删除的点，计算包含该点的正方形数量
   • 但这样会过度减去包含多个被删除点的正方形

3. 应用容斥原理修正

   • 加上包含两个被删除点的正方形数量
   • 减去包含三个被删除点的正方形数量
   • 加上包含四个被删除点的正方形数量

关键技术点

1. 几何关系判断

   • 给定两个点，可以确定另外两个点的位置（可能有两种正方形）
   • 通过坐标变换计算正方形的另外两个顶点

2. 高效查询

   • 使用哈希表存储被删除的点，实现 $O(1)$ 时间查询
   • 避免对每个可能的正方形进行暴力枚举

3. 组合计数优化

   • 利用对称性和数学公式减少计算量
   • 对重复计数的情况使用乘法逆元进行修正

算法复杂度

• 时间复杂度：主要取决于 $K^2$ 的循环，适用于 $K$ 较小的情况
• 空间复杂度：$O(K)$ 存储被删除的点

总结

本题通过组合数学和容斥原理相结合的方法，巧妙地解决了大规模网格中点删除后的正方形计数问题。关键在于将复杂的几何计数转化为系统的容斥过程，既保证了正确性，又控制了计算复杂度。