1. 问题背景与核心挑战ABC202F - Integer Convex Hull 是 AtCoder Beginner Contest 202 的压轴题一道将计算几何与组合计数深度融合的难题。题目本身并不要求我们真的去画出一个凸包而是要求我们计算在给定平面上 N 个整点坐标均为整数中能够选出多少个不同的点集使得这些点构成的凸包的面积的两倍是一个整数。初看这个条件“面积的两倍为整数”有些奇怪但如果你熟悉计算几何中的鞋带公式Shoelace Formula就会立刻明白它的用意。鞋带公式计算出的面积可能是一个小数但“面积的两倍”永远是一个整数对于整点构成的简单多边形。题目真正的限制是这个整数必须是奇数偶数不它要求这个整数本身是一个整数——这听起来像是一句废话但关键在于题目允许凸包退化成一条线段甚至一个点。对于非退化的凸多边形面积两倍自然是整数但对于退化情况面积为零两倍也为零同样是整数。因此题目实际上是在计算所有可能的点集其凸包可能是退化的的顶点集。然而直接枚举所有点集是 2^N 的复杂度显然不可行。这就需要我们深入挖掘“凸包”和“整点”的性质将其转化为一个可计数的结构性问题。这道题的魅力在于它巧妙地避开了复杂的凸包构造算法转而考察对凸包序的深刻理解以及通过排序和动态规划来计数的能力。2. 核心思路与问题转化解决此题的关键一步是进行问题转化。我们不是去枚举哪些点被选中而是去枚举凸包的形状更具体地说是枚举凸包的顶点序列。2.1 从凸包到有序顶点序列对于一个点集 S其凸包的顶点按逆时针或顺时针顺序排列形成一个环。如果我们固定一个起点就可以将这个环打开变成一个序列。题目要求计数不同的点集但不同的点集可能有相同的凸包顶点集。因此我们可以先计算以某个特定顶点序列为凸包的点集有多少个然后再对所有可能的顶点序列求和。但是直接枚举所有可能的顶点序列即所有可能的凸多边形依然非常困难。我们需要一个更结构化的方法。2.2 极角排序与动态规划状态设计一个经典的技巧是固定凸包上的一个点作为原点极点。假设我们固定点 O 作为凸包上的一个点并且我们强制它必须被选中作为凸包顶点。然后我们将所有其他点按照相对于点 O 的极角进行排序。现在考虑从点 O 出发的凸包。由于凸包的凸性当我们逆时针遍历凸包时经过的点的极角是单调递增的。这意味着如果我们把点按照极角排序后凸包剩下的顶点必然是这个序列的一个单调递增子序列在极角意义上。但这还不够因为凸包还要求所有点都在凸包的边“左侧”对于逆时针凸包。这引出了动态规划的状态定义。状态设计 令dp[i][j]表示在极角排序后的点序列中我们构建了一个凸链这个链的最后一个点是i倒数第二个点是j其中点 O, j, i 按顺序构成链的一部分且满足凸性即点 O, j, i 是逆时针的并且所有链上的点都满足凸性条件。这个状态的值表示以 O 为起点以i为当前终点且上一条边是 (j, i) 的凸链的数量。为什么这样设计因为凸包可以看作是从 O 出发逆时针走最后回到 O 的一个环。我们的dp状态在追踪这个行走路径的一部分。当我们想从当前链的终点i添加一个新点k时我们必须检查点k的极角大于点i的极角单调性。点k必须位于有向边 (j, i) 的左侧即向量 (j-i) 和向量 (i-k) 的叉积为正这样才能保证凸性。2.3 转移方程与最终计数转移方程可以表示为dp[i][k] dp[j][i]其中转移必须满足上述两个几何条件。初始化时对于排序后极角最小的那些可以直接从 O 连出去的点i我们可以设置dp[O][i] 1这里为了理解方便将 O 视为一个特殊索引实际实现中可能需要调整。最终凸包的数量如何统计对于一个固定的起点 O我们遍历所有可能的终点i和倒数第二个点j。如果从i能够合法地连回起点 O即点 O 位于边 (j, i) 的左侧且极角条件满足那么dp[j][i]就对应了一个以 O 为顶点的凸包三角形或更多边形。将这些dp[j][i]累加起来就得到了以 O 为顶点的所有非退化凸包的数量。退化情况的处理 题目要求包含点和线段的情况。如何计数单点每个点自身就是一个凸包。共有 N 种。线段任意两个点都可以构成一条线段其凸包就是这条线段。共有 C(N, 2) 种。但需要注意如果三点共线其中间的点不会成为凸包顶点但线段本身仍然被更外侧的两点所定义的凸包所覆盖。在我们的 DP 计数中线段通常不会被计入因为我们的 DP 要求构成至少一个三角形有面积的凸包。因此我们需要单独加上线段的数量。所以最终答案 (所有非退化凸包的数量之和) N C(N, 2)。2.4 算法复杂度与优化直接实现上述 DP 是 O(N^3) 的复杂度枚举起点 O (N种)然后对剩余点排序 (O(N log N))再进行 O(N^2) 的 DP 状态转移状态 O(N^2)每个状态转移需要枚举前驱点看似 O(N^3)。对于 N 最大为 80 的数据范围O(N^4) 是不可接受的。但我们可以优化。对于固定的 O我们已经按极角排序。在计算dp[i][k]时我们需要对所有满足j i k且几何条件成立的j进行累加。这可以通过在遍历时维护前缀信息来优化。更常见的实现是采用 O(N^3) 的算法枚举 O (N)枚举 i (O(N))枚举 k (O(N))然后对于每个 (i, k) 对去累加所有合法的 j。由于 N8080^3 512,000再乘以枚举起点 O 的 80大约是 4000 万量级在 AtCoder 的时间限制2秒下用 C 实现并注意常数优化是可以通过的。关键在于对于每个 (i, k)我们需要快速判断哪些 j 是合法的这通常需要预计算叉积符号。3. 实现细节与几何要点3.1 点的表示与叉积使用整数坐标并定义long long类型存储坐标和叉积结果防止溢出。struct Point { long long x, y; Point operator-(const Point p) const { return {x - p.x, y - p.y}; } long long cross(const Point p) const { return x * p.y - y * p.x; } // 叉积 };叉积a.cross(b)的意义结果 0: 向量 b 在向量 a 的逆时针方向左侧。结果 0: 向量 b 在向量 a 的顺时针方向右侧。结果 0: 两向量共线。在判断点k是否在有向边 (j, i) 的左侧时就是判断向量(i - j)与向量(k - i)的叉积是否大于 0。3.2 极角排序与处理共线以点 O 为原点计算其他点的相对向量p - O。极角排序通常使用atan2函数但由于坐标是整数为了避免浮点数精度问题我们可以使用叉积来比较极角。我们可以通过判断两个向量(p1 - O)和(p2 - O)的叉积符号来比较它们相对于 O 的极角顺序。如果叉积 0则p1在p2的逆时针方向。但直接这样排序需要处理象限。一个更稳健的方法是先按象限排序再按叉积排序。或者对于 N80 的规模使用atan2配合long double通常也足够安全但整数叉积比较是绝对精确的。一个至关重要的细节当有多个点与 O 共线时如何排序我们需要将它们按到 O 的距离排序并且只保留距离 O 最远的那个点作为该方向上的“候选凸包顶点”因为凸包顶点一定是共线点中最外层的点。在 DP 过程中中间的那些共线点不能被选为凸包顶点但它们可以被包含在凸包内部。在我们的计数中我们只关心凸包顶点构成的集合。因此在预处理时对于每个起点 O我们可以也必须过滤掉那些与 O 共线但不是最外层的点否则它们会被错误地计入凸包顶点序列导致重复计数或错误计数。3.3 动态规划实现框架以下是算法的大致框架省略了部分边界条件处理long long ans 0; // 1. 单独的点 ans N; // 2. 线段 ans N * (N - 1) / 2; for (int origin 0; origin N; origin) { vectorPoint pts; vectorint idx_map; // 可选记录原索引 // 收集其他点并计算相对坐标 for (int i 0; i N; i) { if (i origin) continue; pts.push_back(points[i] - points[origin]); // 这里可以处理共线点只保留极角相同且距离最远的点 } // 对 pts 进行极角排序 sort(pts.begin(), pts.end(), [](const Point a, const Point b) { int ha get_half(a), hb get_half(b); // 判断象限 if (ha ! hb) return ha hb; return a.cross(b) 0; // 逆时针排序 }); int m pts.size(); vectorvectorlong long dp(m, vectorlong long(m, 0)); // 初始化从原点 O 到每个点 i 的“链” for (int i 0; i m; i) { dp[origin][i] 1; // 注意这里 dp 的第一维实际是“上一个点”的索引我们需要一个特殊值表示原点。通常用二维数组 dp[i][j]其中 i 和 j 是排序后点的索引。 } // 更常见的状态定义dp[i][j] 表示凸链最后两点是 i, j 的方案数。 // 重新初始化对于所有 jdp[origin][j] 1? 不我们需要一个虚拟的“起点之前”的点。 // 让我们采用 dp[i][j]: 以 i 为倒数第二个点j 为最后一个点的凸链数。 // 初始化对于所有从原点 O 可见的点 j即没有其他点在与 O 共线且更近的位置设 dp[O][j] 1。 // 实际代码中我们可能用三维数组 dp[o][i][j]但这样空间太大。通常做法是枚举起点 O 时重新编号点。 // 简化描述核心转移 // 假设点已经排序为 0,1,2,...,m-1。 // 我们维护一个三维数组 dp[i][j]其中 i j。 // 初始化对于所有 jdp[0][j] 1? 不对。我们需要一个虚拟的“-1”点作为起点。 // 标准做法使用二维 DPdp[i][j] 表示以 i 和 j 为最后两个点的凸链数i j。 // 初始化dp[i][j] 1 如果点 O, i, j 是逆时针的即叉积 0。 // 转移对于所有 i j k如果 (i,j,k) 满足凸性即叉积(i,j,k)0则 dp[j][k] dp[i][j]。 // 预计算叉积符号表 ccw[i][j][k] 表示向量(ij)叉乘向量(ik)的符号 vectorvectorvectorbool valid(m, vectorvectorbool(m, vectorbool(m, false))); for (int i 0; i m; i) { for (int j 0; j m; j) { if (i j) continue; for (int k 0; k m; k) { if (k i || k j) continue; if ((pts[j] - pts[i]).cross(pts[k] - pts[j]) 0) { // 点 i, j, k 是逆时针的 valid[i][j][k] true; } } } } vectorvectorlong long dp(m, vectorlong long(m, 0)); // 初始化所有满足点 O, i, j 逆时针的 (i, j) 对 for (int i 0; i m; i) { for (int j i1; j m; j) { // 这里需要判断原点 O 到 i, j 的向量。实际上原点 O 是 (0,0)。 // 所以判断 (pts[i]) 和 (pts[j]) 的叉积不应该是判断 (0,0), pts[i], pts[j] 的逆时针。 // 即 pts[i].cross(pts[j]) 0 if (pts[i].cross(pts[j]) 0) { dp[i][j] 1; } } } // 转移 for (int i 0; i m; i) { for (int j i1; j m; j) { if (dp[i][j] 0) continue; for (int k j1; k m; k) { if (valid[i][j][k]) { dp[j][k] dp[i][j]; } } } } // 统计以 O 为顶点的凸包数量 for (int i 0; i m; i) { for (int j i1; j m; j) { if (dp[i][j] 0) continue; // 检查是否能够闭合即从 j 连回原点 O 是否满足凸性 // 需要判断点 i, j, O 是否构成逆时针。但 O 是原点 (0,0)。 // 判断向量 (pts[j] - pts[i]) 和 (Point(0,0) - pts[j]) 的叉积即 (pts[j] - pts[i]).cross(-pts[j]) // 等价于判断 (pts[i] - pts[j]).cross(pts[j]) 0 我们直接用预计算的 valid 表但需要包含原点。 // 更简单判断 pts[i].cross(pts[j]) 0 已经在初始化时保证了。闭合条件需要额外判断。 // 实际上闭合条件要求点 i, j, O 是逆时针的并且从 j 到 O 的边不会“包住”任何点但这由 DP 过程保证因为所有点都在凸包内部或边上。 // 一个充分条件是对于原点 O有 (pts[j] - pts[i]).cross(-pts[j]) 0即 (pts[i] - pts[j]).cross(pts[j]) 0。 // 我们可以在循环外预计算一个 close[i][j] 表示从 j 能否连回 O。 // 这里为了清晰我们简化处理如果 pts[i].cross(pts[j]) 0 且从 j 到 O 的向量与最后一条边满足凸性则累加。 // 一个常见的写法是在转移完成后对于所有 (i,j)如果能够从 j 连回 O即向量(pts[j]) 在向量(pts[i]-pts[j]) 的左侧则将 dp[i][j] 加入答案。 // 判断条件 (pts[j] - pts[i]).cross(Point(0,0) - pts[j]) 0 - (pts[j] - pts[i]).cross(-pts[j]) 0 - (pts[i] - pts[j]).cross(pts[j]) 0? 这里容易出错。 // 让我们推导我们希望点 i, j, O 是逆时针排列。即向量 (j-i) 在向量 (j-O) 的逆时针方向不对。 // 三个点 A, B, C 逆时针等价于 (B-A).cross(C-A) 0。 // 这里 Ai, Bj, CO(0,0)。所以条件是(pts[j]-pts[i]).cross(Point(0,0)-pts[i]) 0 - (pts[j]-pts[i]).cross(-pts[i]) 0 - (pts[i]-pts[j]).cross(pts[i]) 0。 // 即判断 (pts[i] - pts[j]).cross(pts[i]) 0。 Point vec_ij pts[j] - pts[i]; Point vec_io Point(0,0) - pts[i]; // 即 -pts[i] if (vec_ij.cross(vec_io) 0) { ans dp[i][j]; } } } }注意以上代码框架是一个概念性展示实际实现需要处理很多细节例如点的去重共线、索引映射、模运算因为答案可能很大等。3.4 模运算与答案输出由于答案可能非常大题目通常要求对某个质数如 998244353取模。在 DP 的每一步加法中都需要进行取模操作。4. 常见难点与调试技巧4.1 共线点的处理这是本题最容易出错的地方。假设点 O, A, B 共线且 B 在 OA 的延长线上即 |OB| |OA|。在构建凸包时A 不应该成为凸包顶点只有 O 和 B 是顶点。在我们的 DP 中如果我们将 A 和 B 都作为候选点那么我们会错误地计算出包含 A 作为顶点的“凸包”。因此在极角排序后对于极角相同的点我们只保留距离 O 最远的那个点用于 DP 计算。但是这带来了另一个问题当我们固定不同的起点 O 时被过滤掉的点集是不同的。因此必须在每次枚举新的起点 O 时重新进行极角排序和共线点过滤。4.2 凸包退化与计数去重我们的 DP 计算了所有以 O 为顶点的凸包至少三个点。当凸包是三角形时它会被它的三个顶点各作为起点计算一次。当凸包有 K 个顶点时它会被计算 K 次每个顶点作为起点一次。因此最后累加的ans是每个凸包被重复计数的总和。我们需要除以每个凸包的顶点数吗不题目要求的是不同的点集数量而不是凸包形状数量。我们的计数方式固定起点 O 的 DP直接计数的是以 O 为顶点的凸包点集。当我们对所有 O 求和后一个由 K 个顶点构成的凸包点集恰好被计算了 K 次因为它的每个顶点都作为起点 O 被计入一次。所以我们最终累加的ans就是所有非退化凸包点集的数量无需额外去重。这是一个非常精妙的性质。4.3 时间复杂度与常数优化O(N^4) 的朴素循环枚举 O, i, j, k对于 N80 是危险的。我们需要 O(N^3) 的算法。上述框架中预计算valid[i][j][k]是 O(N^3)DP 转移是 O(N^3)三层循环 i, j, k。加上外层枚举起点 O总复杂度是 O(N^4)。但实际上我们可以将valid表的计算放到枚举 O 的外层循环中这样总复杂度仍然是 O(N^4)但常数较小。对于 N8080^4 约 4000 万次运算在精心实现的 C 中勉强可以接受但 AtCoder 的 Python 可能不行。更优的做法是在枚举 O 后我们只对 m N-1 个点进行 O(m^3) 的操作总复杂度约为 O(N * (N-1)^3) ≈ O(N^4)。在实际操作中需要避免不必要的内存分配和拷贝使用原生数组或vectorvectorint并注意局部性。一个重要的优化是在 DP 转移时对于固定的 j 和 k我们需要累加所有满足条件的 i。我们可以预先对每个 (j, k) 对计算出所有合法的 i 的列表这样在转移时可以直接遍历这个列表而不是再次遍历所有 i。这可以将最内层循环的复杂度从 O(N) 降到平均 O(1) 或 O(log N)但需要额外的预处理空间。4.4 精度问题尽管我们使用整数运算但在判断三点共线叉积为0时需要特别小心。对于共线点我们必须按照距离排序并只保留最远的点。判断距离时使用平方距离dx*dx dy*dy进行比较避免浮点数。5. 完整代码实现参考C以下是结合了上述所有要点的 C 实现参考。它包含了共线点处理、模运算并尽量优化了常数。#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); } ll cross(const Point p) const { return x * p.y - y * p.x; } ll dot(const Point p) const { return x * p.x y * p.y; } bool operator(const Point p) const { return x p.x y p.y; } bool operator!(const Point p) const { return !(*this p); } }; // 判断点 b 是否在有向边 a-c 的左侧不包含线上 bool isLeft(const Point a, const Point b, const Point c) { return (b - a).cross(c - b) 0; } int main() { int N; cin N; vectorPoint pts(N); for (int i 0; i N; i) { cin pts[i].x pts[i].y; } ll ans 0; // 1. 单个点 ans (ans N) % MOD; // 2. 两个点构成的线段 ans (ans (ll)N * (N - 1) / 2 % MOD) % MOD; // 枚举每个点作为凸包上的固定点 O for (int origin 0; origin N; origin) { vectorPoint vecs; // 收集相对于原点 O 的向量并处理共线点 mappairll, ll, Point farthest; // 对于每个方向约化向量保留距离最远的点 for (int i 0; i N; i) { if (i origin) continue; Point v pts[i] - pts[origin]; ll g gcd(abs(v.x), abs(v.y)); if (g ! 0) { v.x / g; v.y / g; } auto key make_pair(v.x, v.y); // 如果这个方向已经有向量保留距离平方更大的 if (farthest.find(key) farthest.end()) { farthest[key] pts[i] - pts[origin]; } else { Point cur_vec pts[i] - pts[origin]; if (cur_vec.dot(cur_vec) farthest[key].dot(farthest[key])) { farthest[key] cur_vec; } } } // 将过滤后的向量放入 vecs for (auto kv : farthest) { vecs.push_back(kv.second); } int m vecs.size(); if (m 2) continue; // 无法构成至少三角形的凸包 // 极角排序 sort(vecs.begin(), vecs.end(), [](const Point a, const Point b) { int ha (a.y 0 || (a.y 0 a.x 0)) ? 1 : 0; int hb (b.y 0 || (b.y 0 b.x 0)) ? 1 : 0; if (ha ! hb) return ha hb; return a.cross(b) 0; }); // 预计算叉积符号表 left[i][j][k]点 i,j,k 是否逆时针 (i-j-k) // 为了节省空间和时间我们可以在 DP 时实时计算或者预计算一个二维表 ccw[i][j] 表示从 i 到 j 的向量 // 这里我们采用实时计算但预先计算向量差以加速。 // 我们更常用的是预计算一个表 ok[i][j][k]。 // 由于 m 79m^3 ~ 500,000可以接受。 vectorvectorvectorbool ok(m, vectorvectorbool(m, vectorbool(m, false))); for (int i 0; i m; i) { for (int j 0; j m; j) { if (i j) continue; for (int k 0; k m; k) { if (k i || k j) continue; if (isLeft(vecs[i], vecs[j], vecs[k])) { ok[i][j][k] true; } } } } // DP: dp[i][j] 表示以 i, j 为最后两个点的凸链数量 (i j) vectorvectorll dp(m, vectorll(m, 0)); // 初始化所有满足原点 O, i, j 逆时针的 (i, j) for (int i 0; i m; i) { for (int j i1; j m; j) { // 判断 (0,0), vecs[i], vecs[j] 是否逆时针 if (vecs[i].cross(vecs[j]) 0) { dp[i][j] 1; } } } // 转移 for (int i 0; i m; i) { for (int j i1; j m; j) { if (dp[i][j] 0) continue; for (int k j1; k m; k) { if (ok[i][j][k]) { dp[j][k] (dp[j][k] dp[i][j]) % MOD; } } } } // 统计闭合凸包 for (int i 0; i m; i) { for (int j i1; j m; j) { if (dp[i][j] 0) continue; // 检查能否从 j 连回原点 O即点 i, j, O 是否逆时针 // 条件 (vecs[j] - vecs[i]).cross(Point(0,0) - vecs[j]) 0 Point v1 vecs[j] - vecs[i]; Point v2 Point(0,0) - vecs[j]; // -vecs[j] if (v1.cross(v2) 0) { ans (ans dp[i][j]) % MOD; } } } } cout ans % MOD endl; return 0; }重要提示上述代码中的isLeft函数判断严格左侧大于0这意味着如果三点共线该转移不会发生。这符合凸包顶点的定义共线的中间点不是顶点。在初始化dp[i][j]时我们要求vecs[i].cross(vecs[j]) 0同样排除了共线情况。这确保了我们的 DP 只计数非退化的凸多边形。6. 总结与扩展思考ABC202F 是一道综合性极强的题目它要求选手理解凸包的几何定义及其与极角排序的关系。掌握利用动态规划计数有序序列的技巧将几何条件转化为状态转移的条件。细致处理边界情况特别是共线点的过滤这是正确计数的关键。优化算法复杂度将看似 O(N^4) 的问题通过预计算和合理状态设计控制在可接受范围内。解决此题后可以对类似的计算几何计数问题有更深的理解。例如如何计算凸多边形的数量如何计算星形多边形的数量其核心思想都是固定一个点然后通过极角排序将环状结构转化为线性序列上的 DP 问题。在调试此类问题时建议从小规模数据N4,5开始手动计算所有可能的凸包并与程序输出对比。同时可以编写一个暴力枚举所有点集并求凸包的对照程序对于 N10 左右用于验证 DP 算法的正确性。注意处理模运算时加法和乘法都要及时取模防止中间结果溢出long long范围在本题坐标和 N 范围内一般不会但养成好习惯。