ABC202F 整数凸包计数：从凸包到动态规划的几何与数论结合

1. 问题引入从“凸包”到“整数凸包”的跨越做算法竞赛的朋友对“凸包”这个概念肯定不陌生。无论是计算几何的入门题还是各种需要求点集外围轮廓的场景凸包算法比如 Graham Scan 或 Andrew 算法都是基础中的基础。但 ABC202F 这道题把“凸包”这个经典问题推向了一个新的维度整数凸包。乍一看标题 “Integer Convex Hull”你可能会想凸包的点坐标本来就是整数啊这有什么特别的这里的“整数”指的并不是坐标而是凸包的面积。题目要求我们计算给定一个平面上的整数点集能构成多少个面积是整数的凸多边形。这立刻将问题从一个纯几何的构造问题转变成了一个融合了数论判断面积是否为整数、组合数学枚举子集和动态规划的综合性难题。我最初看到这道题时感觉它像是“计算几何”和“计数DP”生出的一个“怪胎”。常规的凸包计数问题往往关注凸包本身是否存在或者凸包的大小周长、面积。而这里面积是否为整数成为了一个核心的筛选条件。这意味着我们在枚举所有可能的点集构成凸包时不能只关心几何属性还得拿起数论的放大镜去审视那个由叉积和除以2得来的面积值。这种跨领域的结合正是题目 ABC202F 的魅力与难点所在。它考察的不仅仅是你会不会写凸包算法更考察你能否将几何性质转化为便于计数的模型以及如何高效地处理“整数面积”这个约束条件。接下来我们就一起拆解这个“怪胎”看看如何将它驯服。2. 核心思路拆解如何系统化地计数面对“数出所有面积为整数的凸多边形”这种问题暴力枚举所有点集子集显然是死路一条。点的数量 N 最大为 80子集数量是 2^80这是一个天文数字。我们必须寻找一个系统化的、能利用凸包几何特性的计数方法。一个关键的突破口是一个凸多边形由其顶点唯一确定并且这些顶点按逆时针或顺时针顺序排列后其内部的所有点都不会影响这个凸多边形的形状。这引出了一个非常重要的计数技巧以凸包的最左下角点通常取 x 最小相同时 y 最小作为基准点进行极角排序后动态规划。具体思路分步如下2.1 排序与基准点首先我们选取一个点 O 作为“锚点”。通常选择坐标字典序最小的点即 x 最小x 相同时 y 最小。这个点有一个很好的性质在任何一个以其为顶点的凸多边形中它一定是凸包上的一个顶点特别是它通常可以作为起点。固定 O 之后我们将其余的点按照相对于 O 的极角进行排序。这样任何以 O 为顶点的凸多边形其顶点在排序后的序列中极角序是单调递增的。2.2 动态规划状态设计这是最精妙的部分。我们定义 DP 状态dp[i][j]表示以 O 为起点当前凸包的最后一条边是(O, i)并且包括点 i 在内能够形成的所有凸多边形的某种“权重”或“计数”。这里 i 是极角排序后某个点的索引。但这样还不够因为凸包是“凸”的我们需要确保新增的点不会破坏凸性。如何刻画“凸性”这需要用到叉积。假设当前凸包的最后一条边是(k, i)我们要加入下一个点 j。那么向量(k-i)和(i-j)的叉积必须大于 0对于逆时针凸包这样才能保证 j 在 i 的“左侧”从而保持凸性。因此更准确的状态是dp[i][j]表示以 O 为起点当前凸包的最后一条边是(i, j)且该凸包包括 O, i, j是凸的所对应的方案数。这里 i 和 j 都是极角排序后的点索引且 i j因为极角递增。2.3 状态转移转移方程是这类计数问题的核心。对于状态dp[i][j]我们可以考虑所有可能的“下一个点” k其中 k j极角序在 j 之后。如果点 k 满足凸性条件即向量(j - i)与(k - j)的叉积大于 0保证是左转维持凸性那么我们就可以从dp[i][j]转移到dp[j][k]并且将dp[i][j]的方案数累加到dp[j][k]中。2.4 处理面积整数约束现在引入核心约束面积必须是整数。凸多边形的面积可以通过所有相邻顶点包括首尾相连的叉积之和除以 2 得到鞋带公式。在我们的 DP 过程中面积是随着点的加入而累积的。 我们可以将面积作为一个状态维度。但面积可能很大直接作为数组下标不现实。一个巧妙的处理方法是利用叉积的线性性质将面积对 2 取模。为什么是模 2因为面积 叉积和 / 2。面积是整数的充要条件是叉积和是偶数。因此我们只需要在 DP 过程中维护叉积和除以 2 之前的原始叉积和记为 S的奇偶性即可。如果最终 S 是偶数那么面积就是整数。因此我们将 DP 状态扩展为dp[i][j][p]其中 p 0 或 1表示当前叉积和 S 的奇偶性。转移时当加入点 k新的叉积会增加cross(i, j, k)这里cross(i, j, k)表示向量(j-i)和(k-j)的叉积注意实际累积的是由 O, i, j, ... 围成的多边形的有向面积的两倍转移时需要仔细计算新增的三角形面积对应的叉积。更准确地说从(i, j)到(j, k)为整个多边形新增的面积是三角形(O, j, k)的面积不对这样会重复计算。正确的累积方式是整个多边形的有向面积两倍S在加入点 k 后新增的部分是cross(i, j, k)。这个结论需要一点推导。假设当前凸包顶点序列是O - v1 - v2 - ... - vm其中vm jv_{m-1} i。根据鞋带公式总面积两倍S包含项... cross(v_{m-1}, v_m) cross(v_m, O)。当我们加入点 k 作为v_{m1}时需要去掉cross(v_m, O)并新增cross(v_{m-1}, v_m, v_{m1})和cross(v_{m1}, O)。但注意在我们的 DP 状态dp[i][j]中我们隐含地认为凸包最后会闭合到 O。所以我们实际上维护的S是不包含最后一条闭合边(j, O)的叉积。这样加入点 k 时新增的叉积就是cross(i, j, k)。而最后当凸包闭合时我们需要额外加上cross(j, O, O)不对闭合边是(最后一个点, O)其叉积为cross(最后一个点, O)。为了统一一种常见的处理技巧是DP 状态中的S记录从 O 开始按顺序到当前点 j 为止所有相邻顶点与 O 构成的三角形的叉积累积和。另一种更通用的方法是状态中的S直接记录当前已构成的凸多边形从 O 到 i 到 j的叉积和两倍面积。当从(i, j)转移到(j, k)时新的叉积和S S cross(i, j, k)。这个cross(i, j, k)就是向量(j-i)和(k-j)的叉积。让我们验证一下设凸包为 O - A - B - C闭合。总面积两倍 S_total cross(O,A) cross(A,B) cross(B,C) cross(C,O)。 如果我们定义状态 dp[A][B] 对应的 S 为 S_AB cross(O,A) cross(A,B)。 那么从 dp[A][B] 转移到 dp[B][C] 时新增的叉积是 cross(B, C)。新的 S_BC S_AB cross(B, C) cross(O,A) cross(A,B) cross(B,C)。这正好是闭合前缺少cross(C,O)的项。所以最终对于一个闭合的凸包O - i - j - ... - last我们在 DP 中得到的最终状态dp[last_prev][last]对应的 S 值还需要加上cross(last, O)才能得到完整的 S_total。因此判断最终凸包面积是否为整数需要检查(S_final cross(last, O))是否为偶数。2.5 初始化与答案统计初始化对于排序后的任意两点 i, j (i j)如果 O, i, j 不共线共线会导致面积为0但可能破坏凸性定义通常共线点需要特殊处理或剔除那么我们可以初始化一个三角形O - i - j。对应的叉积和 S_init cross(O, i) cross(i, j)。注意这里 S_init 不包含cross(j, O)。所以dp[i][j][S_init % 2] 1。答案统计对于任意最终状态dp[i][j][p]它代表了一个以 O 为起点i 为倒数第二个点j 为最后一个点的凸链未闭合。要形成一个闭合的凸多边形我们需要满足从 j 连回 O 时不能破坏凸性。即向量(i, j)到(j, O)的叉积也要大于 0。整个多边形的面积两倍S_total S_current cross(j, O)必须是偶数即(p cross(j, O)) % 2 0。满足以上条件的dp[i][j][p]就可以贡献到最终答案中。注意这样统计的是所有顶点数大于等于3的凸多边形。三角形(O, i, j)也包含在其中其对应的 dp 状态在初始化时就被创建了。2.6 去重与共线处理由于我们固定了起点 O并且按极角排序每个凸多边形只会被以 O 为起点的唯一一种顶点序列表示出来因此不会重复计数。 对于共线点需要小心。如果三个点共线叉积为0。在凸包定义中共线的点通常只保留端点。在我们的计数中如果允许共线点出现在凸包上会导致重复计数一个凸多边形有多种顶点表示。因此通常的做法是在极角排序后对于极角相同的点按照到 O 的距离由近到远排序。在 DP 转移时如果cross(i, j, k) 0说明三点共线我们不予转移或者根据题目要求特殊处理。在 ABC202F 中通常的题解都要求严格凸所有内角小于180度因此叉积必须严格大于0等于0的情况共线不转移。3. 算法实现细节与踩坑点理解了思路实现起来还有一大堆细节等着你。下面我结合自己的调试经历把几个容易出错的地方拎出来说说。3.1 极角排序与精度问题点的坐标范围是绝对值不超过 10^8 的整数。直接用atan2(y, x)计算极角会引入浮点数可能带来精度误差在比较大小时造成错误排序。这是计算几何的老问题了。绝对不要用浮点数做极角排序正确的做法是使用叉积进行排序。对于两个点 A 和 B均非基准点 O比较它们相对于 O 的极角可以通过计算cross(OA, OB)来判断。如果叉积大于 0说明 OB 在 OA 的逆时针方向即 B 的极角大于 A。如果叉积等于 0说明二者共线此时按照到 O 的距离排序距离近的排在前面这样在 DP 时如果遇到共线点我们会先处理离 O 近的点便于后续判断。// 假设点结构体为 Point { long long x, y; } // 基准点为 points[0] vectorPoint pts; // 所有点 sort(pts.begin() 1, pts.end(), [](const Point a, const Point b) { long long cr cross(points[0], a, b); // cross(O, a, b) if (cr ! 0) return cr 0; // 逆时针排序所以大于0时a在b的逆时针方向a的极角小 // 注意当cross0向量a在向量b的逆时针方向通常我们认为a的极角更小。 // 但这里要统一顺序。更安全的写法是 // return cr 0; // 共线时按距离排序 return dist2(points[0], a) dist2(points[0], b); });这里有个常见的混淆点cross(O, a, b) 0到底意味着 a 的极角大还是小这取决于你的坐标系。在常见的屏幕坐标系y轴向下和数学坐标系y轴向上下结果是反的。一个可靠的方法是自己画两个点测试一下。在算法竞赛中通常约定使用数学坐标系。所以cross(O, a, b) 0表示从 OA 转到 OB 是逆时针即 B 的极角大于 A。因此如果我们想让极角从小到大排序应该让cross(O, a, b) 0时返回false即认为 a 应该在 b 后面。为了避免混乱我建议这样写比较函数auto cmp [](const Point a, const Point b) { int qa quadrant(a - O), qb quadrant(b - O); if (qa ! qb) return qa qb; // 先按象限排序 long long cr cross(O, a, b); if (cr ! 0) return cr 0; // 在同一象限逆时针方向极角增大的排在后面这里需要仔细。 // 更稳妥的写法直接判断叉积 // 我们希望极角小的排在前面。 // 如果 cross(O, a, b) 0说明 b 在 a 的逆时针方向即 a 的极角更小所以 a 应该排在 b 前面。 // 因此当 cross 0 时返回 truea b。 long long cr cross(O, a, b); if (cr ! 0) return cr 0; return dist2(O, a) dist2(O, b); };在实践中我强烈推荐使用以下写法它避免了象限判断直接通过叉积和点积来比较逻辑清晰bool cmp(const Point a, const Point b) { Point pa a - O, pb b - O; if (pa.y 0 pb.y 0) return true; // a在上半平面b在下半平面 if (pa.y 0 pb.y 0) return false; if (pa.y 0 pb.y 0) { // 都在x轴上 if (pa.x 0 pb.x 0) return true; if (pa.x 0 pb.x 0) return false; return norm(pa) norm(pb); // 同向按模长 } long long cr cross(pa, pb); if (cr ! 0) return cr 0; // 逆时针排序对于上半平面从左到右下半平面从右到左。 return norm(pa) norm(pb); // 共线按距离 }这个比较函数能正确处理所有情况是经过无数竞赛选手验证的“轮子”。3.2 DP 转移的顺序与复杂度状态数是 O(N^2 * 2)转移需要枚举 i, j, k复杂度是 O(N^3)。N80 时80^3 512,000再乘以常数 2完全在可接受范围内。 实现时最外层的循环应该是按极角序枚举中间点 j。对于每个 j我们枚举所有可能的 i (i j)然后枚举所有可能的 k (k j)。这样能保证拓扑顺序。vector dp(n, vector(n, arraylong long, 2{0, 0})); // dp[i][j][0/1] // 初始化 for (int i 1; i n; i) { for (int j i1; j n; j) { if (cross(O, pts[i], pts[j]) 0) continue; // 共线不构成三角形 long long s_init cross(O, pts[i]) cross(pts[i], pts[j]); dp[i][j][s_init 1] 1; } } // 转移 for (int j 1; j n; j) { for (int i 1; i j; i) { if (dp[i][j][0] 0 dp[i][j][1] 0) continue; for (int k j1; k n; k) { if (cross(pts[i], pts[j], pts[k]) 0) continue; // 非左转不满足凸性 long long add cross(pts[i], pts[j], pts[k]); for (int p 0; p 2; p) { if (dp[i][j][p] 0) continue; int new_p (p add) 1; dp[j][k][new_p] (dp[j][k][new_p] dp[i][j][p]) % MOD; } } } }3.3 答案统计的细节统计答案时需要遍历所有可能的结尾边 (i, j)并判断从 j 连回 O 是否保持凸性以及总面积是否为整数。long long ans 0; for (int i 1; i n; i) { for (int j i1; j n; j) { if (cross(pts[i], pts[j], O) 0) continue; // 闭合边不满足凸性 for (int p 0; p 2; p) { if (dp[i][j][p] 0) continue; long long s_total p cross(pts[j], O); // 注意这里 p 是奇偶性cross是值 // 需要计算 (p cross(pts[j], O)) 的奇偶性 if (( (p cross(pts[j], O)) 1 ) 0) { ans (ans dp[i][j][p]) % MOD; } } } }这里有一个巨大的坑p是奇偶性0或1而cross(pts[j], O)是一个可能很大的整数值。我们不能直接把它们相加。我们需要的是(p cross(pts[j], O))的奇偶性这等价于(p (cross(pts[j], O) 1)) 1。所以判断条件应该写为if ( ((p (cross(pts[j], O) 1)) 1) 0 ) { ans (ans dp[i][j][p]) % MOD; }我当初就在这里 WA 了好几次因为忽略了cross值的奇偶性需要单独取模。3.4 模运算与初始化题目要求对 998244353 取模。所有加法、乘法都要记得取模。初始化dp[i][j][s_init 1] 1时这个 1 就是方案数。 另外注意cross函数可能会返回负数而我们需要的是有向面积的“两倍”的奇偶性。在 C 中负数对 2 取模% 2可能得到 -1 或 1取决于编译器。为了安全地获取奇偶性应该使用(x 1)或者((x % 2) 2) % 2。对于cross这种可能为负的情况最安全的方法是long long cr cross(a, b, c); int parity (cr 1); // 这样对吗如果cr是负数cr 1 的结果 // 实际上对于负数cr 1 的结果也是 0 或 1因为它是对二进制位进行操作。 // 但更清晰且可移植的写法是 int parity ((cr % 2) 2) % 2; // 得到 0 或 1在性能允许的情况下使用(cr 1)是没问题的因为补码表示下奇数的最后一位是1偶数是0这与数值的正负无关。4. 代码实现与模板整合将以上所有思路和细节整合起来我们可以得到一份完整的 AC 代码。下面我给出一个清晰的实现并附上关键注释。#include bits/stdc.h using namespace std; using ll long long; const int MOD 998244353; struct Point { ll x, y; Point() {} Point(ll x_, ll y_) : x(x_), y(y_) {} Point operator-(const Point p) const { return Point(x - p.x, y - p.y); } bool operator(const Point p) const { // 用于找左下角点 return tie(x, y) tie(p.x, p.y); } }; // 叉积 (a - o) x (b - o) ll cross(const Point o, const Point a, const Point b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); } // 两点距离平方 ll dist2(const Point a, const Point b) { ll dx a.x - b.x, dy a.y - b.y; return dx * dx dy * dy; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorPoint pts(N); for (int i 0; i N; i) { cin pts[i].x pts[i].y; } // 将最左下角的点交换到 pts[0] int min_idx 0; for (int i 1; i N; i) { if (pts[i] pts[min_idx]) min_idx i; } swap(pts[0], pts[min_idx]); Point O pts[0]; // 极角排序 (从 pts[1] 开始排) sort(pts.begin() 1, pts.end(), [](const Point a, const Point b) { Point pa a - O, pb b - O; // 处理象限 if (pa.y 0 pb.y 0) return true; if (pa.y 0 pb.y 0) return false; if (pa.y 0 pb.y 0) { if (pa.x 0 pb.x 0) return true; if (pa.x 0 pb.x 0) return false; return dist2(O, a) dist2(O, b); } ll cr cross(O, a, b); if (cr ! 0) return cr 0; // 逆时针排序 return dist2(O, a) dist2(O, b); }); // DP 数组: dp[i][j][parity] , i j // 使用 vector 可能超时N80 N^2 * 2 12800 用数组更快。 // 这里为了清晰用 vector vector dp(N, vector(N, arrayll, 2{0, 0})); // 初始化三角形 (O, i, j) for (int i 1; i N; i) { for (int j i 1; j N; j) { if (cross(O, pts[i], pts[j]) 0) continue; // 共线忽略 ll s_init cross(O, pts[i]) cross(pts[i], pts[j]); dp[i][j][s_init 1] 1; } } // DP 转移 for (int j 1; j N; j) { for (int i 1; i j; i) { if (dp[i][j][0] 0 dp[i][j][1] 0) continue; for (int k j 1; k N; k) { if (cross(pts[i], pts[j], pts[k]) 0) continue; // 非左转 ll add cross(pts[i], pts[j], pts[k]); for (int p 0; p 2; p) { if (dp[i][j][p] 0) continue; int new_p (p (add 1)) 1; dp[j][k][new_p] (dp[j][k][new_p] dp[i][j][p]) % MOD; } } } } // 统计答案 ll ans 0; for (int i 1; i N; i) { for (int j i 1; j N; j) { if (cross(pts[i], pts[j], O) 0) continue; // 闭合边不凸 for (int p 0; p 2; p) { if (dp[i][j][p] 0) continue; // 判断总面积奇偶性: p 是当前链奇偶性还需加上 cross(pts[j], O) 的奇偶性 if (((p (cross(pts[j], O) 1)) 1) 0) { ans (ans dp[i][j][p]) % MOD; } } } } cout ans endl; return 0; }这份代码已经包含了所有核心逻辑。但这里还有一个非常重要的优化复杂度是 O(N^3)对于 N80 是可行的512,000次循环。但内部循环有一些判断可以提前跳出比如如果dp[i][j]全为0就可以跳过。另外cross的计算很频繁可以考虑预计算所有点对的叉积用三维数组cross_val[i][j][k]存储但这会占用 O(N^3) 的内存80^3 * 8字节 ≈ 4MB可以接受能换取一些时间。不过对于这道题不加这个优化也能轻松通过。5. 总结与思维延伸ABC202F 是一道质量非常高的计数 DP 与计算几何结合的问题。它教会我们的不仅仅是某个算法模板更是一种问题转化的思维如何将一个看似复杂的几何计数问题通过固定起点、极角排序、状态设计记录面积奇偶性等手段转化为一个具有最优子结构、可以动态规划解决的问题。回顾整个解题过程关键的思维跳跃点在于固定基准点 O这打破了凸多边形顶点顺序的对称性使得每个凸多边形有了一个唯一的表示起点。极角排序将二维平面上的点转化为一维序列使得凸多边形的顶点在这个序列中是递增的从而可以用序列上的 DP 来刻画。状态设计为dp[i][j]记录以(i, j)为最后一条边的凸链这巧妙地捕捉了凸包的“当前状态”。将整数面积条件转化为奇偶性维护这是数论与几何结合的点睛之笔避免了将巨大的面积值作为状态维度。这道题可以有很多变种。比如如果不是要求面积为整数而是要求面积模某个质数等于某个值呢思路是类似的只需要将状态中的奇偶性维度改为模意义下的值即可。再比如如果要求凸多边形的顶点数恰好为 K 呢我们可以在状态中增加一维表示顶点数。这体现了 DP 的灵活性。在实现层面最大的教训就是注意细节极角排序的比较函数、叉积为0共线的处理、负数奇偶性的判断、答案统计时对闭合边的凸性检查和总面积奇偶性的计算。这些地方只要有一个疏忽就会导致 WA 或者调试半天。最后对于想挑战类似问题的朋友我建议在理解本题的基础上可以去尝试一些经典的凸包计数问题比如计算空凸多边形的数量凸包内部没有其他给定点或者计算面积在某个范围内的凸包数量。这些题目都是基于类似的 DP 框架但会增加额外的约束条件非常锻炼思维。