1. 项目概述从一道竞赛题看凸包计数的核心挑战最近在复盘AtCoder Beginner Contest 202的F题“Integer Convex Hull”时我意识到这道题远不止是一道普通的计算几何练习题。它巧妙地将离散点集的凸包计数问题与组合数学、动态规划中的状态压缩思想结合形成了一个对思维严谨性和代码实现能力都有极高要求的综合性问题。题目大意是给定平面上N个整点坐标均为整数问有多少个非空点集其凸包的顶点恰好都是给定点集中的点并且凸包内部不含边界不包含任何其他给定点。简单说就是统计所有“顶点来自给定集、且内部无其他给定点”的凸多边形有多少个。这听起来像是纯几何的枚举题但N最大可达80暴力枚举所有子集2^80种可能完全不现实。核心难点在于我们不仅要判断一个点集是否能形成符合条件的凸包还要高效地统计所有这样的点集同时避免重复计数例如同一个凸包可能由其顶点集或部分顶点集构成。这道题的魅力在于它迫使你跳出“先找点集再判断凸包”的朴素思维转而从凸包的构建过程入手利用动态规划来“组装”凸包。接下来我将详细拆解解决此问题的完整思路、关键算法原理以及实现中的诸多细节与陷阱。2. 问题核心与数学模型转化2.1 问题重述与严格定义首先我们需要将问题描述转化为更精确的数学模型。设给定的点集为 ( S {P_1, P_2, ..., P_N} )每个点 ( P_i (x_i, y_i) )且 ( x_i, y_i ) 均为整数。我们需要统计所有满足以下条件的点集 ( T \subseteq S )( T ) 非空。( T ) 的凸包的顶点集合恰好等于 ( T )。凸包的内部严格内部不包含边界不包含 ( S ) 中的任何其他点。即 ( S \cap \text{interior}(\text{ConvexHull}(T)) \emptyset )。这里有一个关键解读条件2意味着 ( T ) 中的点必须全部是凸包的顶点不能有位于凸包边或内部的点。条件3意味着这个凸包是“干净的”内部没有其他“杂质”点。2.2 暴力枚举的不可行性与思路转换最直接的想法是枚举 ( S ) 的所有非空子集 ( T )对每个 ( T ) 计算凸包然后检查条件2和3。这显然不可行复杂度为 ( O(2^N \cdot N \log N) )。我们必须寻找更聪明的方法。一个核心观察是一个凸多边形可以由其有序的顶点序列唯一确定。如果我们能按照某种顺序比如极角序来“构建”凸包就可以用动态规划来计数。思路转换如下将问题转化为对凸多边形的计数而不是对点集的计数。规定一个起始点然后按逆时针或顺时针顺序依次添加顶点构建凸包。在构建过程中需要保证新添加的点与当前最后一条边构成的“扇形”区域内不能有其他给定点以满足内部无点的条件。利用动态规划来记录以某个点为起点当前终点是某个点且已经包含了某些点的状态并统计方案数。这引出了本题的核心解法基于极角排序的动态规划DP。3. 算法原理深度剖析3.1 极角排序与状态设计首先我们枚举凸包上的一个“基准点” ( O )。这个点将作为凸包的起点同时也是终点。为了固定顺序我们规定凸包顶点按逆时针方向排列。对于基准点 ( O )我们将其他所有点按照相对于 ( O ) 的极角进行排序。如果极角相同则按距离 ( O ) 由近到远排序。这样我们就建立了一个确定的遍历顺序。接下来定义DP状态 令 ( dp_{start}_{end}_{mask} ) 表示一种可能的“凸包构建路径”的方案数。其中( start )路径的起点即我们枚举的基准点 ( O )。( end )当前路径的最后一个点。( mask )一个比特掩码bitmask表示在路径上包括起点和终点已经使用了哪些点。由于N最大为80直接存2^80的状态是不可能的。这里需要第二个关键观察在构建凸包的一条边时我们只关心这条边“右侧”的点是否被非法包含。对于逆时针凸包其内部始终在边的左侧。因此当我们从点 ( u ) 连接到点 ( v ) 时所有在这条边右侧的点如果被包含在凸包内部就会违反条件3。但是我们并不需要记录所有点的占用情况。我们可以将状态进行简化。考虑一条从 ( O ) 到 ( end ) 的路径它构成了凸包的一部分。如果我们想从 ( end ) 扩展到一个新点 ( next )那么必须满足点 ( next ) 必须位于当前点 ( end ) 的极角序列中在 ( end ) 之后以维持逆时针顺序。三角形 ( (O, end, next) ) 的内部以及边 ( (end, next) ) 的右侧区域不能包含任何其他给定点。如果满足条件那么从状态 ( (O, end, mask) ) 就可以转移到状态 ( (O, next, mask | (1next)) )。然而( mask ) 仍然太大。我们需要思考为了后续扩展的合法性我们真正需要记录的是什么答案是我们只需要记录哪些点已经被选为凸包顶点。因为一旦一个点被选为顶点它就不能再出现在后续任何边的右侧即凸包内部。所以当我们考虑从 ( end ) 走到 ( next ) 时我们需要检查线段 ( (end, next) ) 的右侧是否包含任何已经被选入凸包的点即 ( mask ) 中的点。如果包含那么这个扩展就是非法的因为那个点应该出现在凸包边界上而不是内部。因此( mask ) 记录了当前已使用的顶点集。状态总数是 ( O(N \cdot 2^N) )对于 N80 仍然巨大。3.2 关键优化状态剪枝与计数原则我们需要进一步优化。注意我们的最终目标是计数而不是枚举所有状态。我们可以利用一个常见的技巧固定起点按顺序添加顶点并使用二维DP。重新定义状态令 ( dp[i][j] ) 表示以 ( O ) 为起点( i ) 为终点且( i ) 是当前路径的最后一个点的凸包路径的方案数。这里似乎没有记录使用了哪些点会不会出错关键在于转移条件。当我们从 ( dp[i][j] ) 转移到 ( dp[j][k] ) 即从路径 ... - i - j 扩展到 ... - i - j - k时需要满足点 ( i, j, k ) 相对于 ( O ) 是逆时针排列的即极角递增。三角形 ( (O, j, k) ) 的内部和边 ( (j, k) ) 的右侧不能包含任何在之前路径上出现过的点除了 ( O, i, j ) 本身。这里就体现了“记录已使用点”的必要性。但是我们可以通过预处理和转移时的严格检查来避免显式记录mask。预处理对于任意两个点 ( u, v ) 均不同于 ( O )我们可以预处理出所有位于有向线段 ( \overrightarrow{uv} ) 右侧的点。更具体地说是判断一个点 ( p ) 在有向线段 ( \overrightarrow{uv} ) 的哪一侧。这可以通过计算叉积 ( \overrightarrow{uv} \times \overrightarrow{up} ) 来实现。若叉积大于0则 ( p ) 在左侧对于逆时针凸包这是内部若小于0则在右侧等于0则在线上。我们需要检查的是右侧是否有点。但更重要的是在转移时对于一条新边 ( (j, k) )我们需要确保这条边的右侧没有“不应该在那里的点”。哪些点不应该在那里答案是所有不是 ( k ) 且极角介于 ( j ) 和 ( k ) 之间的点。为什么因为在一个以 ( O ) 为起点的逆时针凸包中所有顶点都按极角排好序。如果存在一个点 ( p )其极角在 ( j ) 和 ( k ) 之间但它又不是 ( k )那么它要么应该是凸包顶点但没被选要么就在凸包内部。如果它在边 ( (j, k) ) 的右侧那就意味着它实际上位于凸包外部这与凸包定义矛盾。如果它在左侧则它可能在凸包内部这需要结合其他边来判断。因此一个更实用的条件是对于转移 ( j - k )所有极角介于 ( j ) 和 ( k ) 之间的点不包括端点都必须位于有向线段 ( \overrightarrow{jk} ) 的左侧。这样这些点才会落在由 ( O, j, k ) 构成的三角形内部或未来的凸包内部而不会“漏”到外面去。我们可以预处理一个布尔数组valid[j][k]表示从 ( j ) 到 ( k ) 的转移是否合法。合法条件为对于所有极角介于 ( j ) 和 ( k ) 之间的点 ( p )有 ( \overrightarrow{jk} \times \overrightarrow{j p} 0 ) 即 ( p ) 在 ( \overrightarrow{jk} ) 左侧。有了这个预处理我们的DP就可以进行了。3.3 动态规划转移方程枚举基准点 ( O )。将其他点按相对于 ( O ) 的极角排序得到序列 ( points[1..M] )其中 ( M N-1 )。初始化DP数组dp为0。dp[i][j]表示一条从 ( O ) 出发到达 ( i )并以 ( j ) 为终点的路径数不这样定义维度不够。我们需要重新思考。更准确的状态定义 我们构建的是一条从 ( O ) 开始在排序后的点序列中跳转的路径。设 ( dp[i][j] ) 表示一条凸包路径该路径的最后一条边是从点 ( i ) 到点 ( j ) 的方案数。其中点 ( i ) 和 ( j ) 都是排序后序列中的点不是原始索引是排序后的索引。初始化对于排序后的每个点 ( i )我们可以认为有一条从“虚拟起点” ( O ) 到点 ( i ) 的边。因此初始化dp[0][i] 1。这里我们用索引0代表基准点 ( O )。转移对于所有满足i j k且valid[j][k] true的三元组我们可以进行转移dp[j][k] dp[i][j]这个转移的含义是如果存在一条路径最后到达了 ( j )且上一条边是 ( i \to j )那么如果 ( j \to k ) 是合法的满足左侧条件我们就可以将路径延伸到 ( k )并以 ( j \to k ) 作为最后一条边。最终答案对于所有合法的、能够闭合回起点 ( O ) 的路径进行统计。即对于某个状态dp[i][j]如果从 ( j ) 到 ( O ) 的转移是合法的即valid[j][O]为真这里需要对 ( O ) 做特殊处理那么这条路径就形成了一个以 ( O ) 为顶点的凸包。我们需要将这些方案数累加起来。但是这里有一个重大问题我们如何表示“闭合回起点 ( O ) ”以及我们这样计数会不会把同一个凸包重复计数多次例如选择不同的起点 ( O )3.4 去重处理与最终计数首先解决重复计数问题。一个凸包有多个顶点如果我们对每个顶点都作为基准点 ( O ) 计数一次那么每个凸包会被计数多次次数等于其顶点数。一个标准的去重方法是在枚举基准点 ( O ) 时只统计那些将 ( O ) 作为凸包中极角最小或字典序最小的顶点的凸包。具体做法是在枚举基准点 ( O ) 时只考虑那些在全局点集中( O ) 是横坐标最小或纵坐标最小或按(x,y)字典序最小的点吗不这不够。因为凸包的“最小”顶点是相对于凸包本身而言的。常用的策略是在枚举基准点 ( O ) 时只将其他点中那些相对于 ( O ) 的极角严格大于0的点纳入排序和DP过程。并且在最后闭合时要求闭合边 ( (last, O) ) 的右侧不能有任何点即闭合边也必须是凸包边。同时在整个DP过程中我们构建的路径始终是“凸”的通过valid数组保证。这样每个凸包只会被其极角最小的顶点 ( O ) 计数到一次。因为如果以凸包的其他顶点作为基准点那么极角最小的顶点相对于那个新基准点将不是它自己我们在初始化或转移时就会将其排除。最终答案是对所有枚举的基准点 ( O ) 计算得到的方案数求和。但要注意我们统计的是凸包的数量而题目要求的是点集的数量。对于一个凸包其对应的点集就是它的顶点集。由于我们构建的每个凸包都是“干净的”内部无点且顶点全是给定点所以凸包和点集是一一对应的。因此我们计数的凸包数就是答案。然而我们还需要考虑退化的凸包——即点集所有点共线的情况。根据凸包定义共线的点集形成的凸包是一条线段其“内部”是空的但“顶点”通常定义为线段的两个端点。题目中“凸包的顶点恰好都是给定点集中的点”对于共线情况如何界定通常在这种计数问题中要求凸包的面积必须大于0即至少需要三个不共线的点才能构成一个凸多边形。因此共线的点集两个点不应被计入。我们的DP方法通常会自动排除这种情况因为需要形成闭合多边形。4. 实现细节与代码剖析4.1 数据结构与预处理首先定义点的结构体并实现基本的向量运算。struct Point { long long x, y; Point() {} Point(long long x, long long y) : x(x), y(y) {} Point operator-(const Point p) const { return Point(x - p.x, y - p.y); } long long cross(const Point p) const { return x * p.y - y * p.x; } // 叉积 long long cross(const Point a, const Point b) const { return (a - *this).cross(b - *this); } // 三点叉积 bool operator(const Point p) const { // 用于排序 return x p.x || (x p.x y p.y); } bool operator(const Point p) const { return x p.x y p.y; } };预处理的关键是计算valid[i][j]。假设我们已经以某个点 ( O ) 为基准将其他点按极角排序得到数组pts大小为m。vectorvectorbool valid(m, vectorbool(m, false)); for (int i 0; i m; i) { for (int j i1; j m; j) { bool ok true; for (int k i1; k j; k) { // 检查极角在i和j之间的所有点k if (orientation(pts[i], pts[j], pts[k]) 0) { // 如果k不在线段(i,j)的左侧 ok false; break; } } valid[i][j] ok; } }其中orientation(a, b, c)计算(b-a) × (c-a)的叉积大于0表示c在ab的左侧等于0表示共线小于0表示在右侧。这里我们要求严格左侧0以确保点严格在内部/左侧。4.2 动态规划实现DP数组dp[i][j]表示最后一条边为(i, j)的凸包路径数。这里i和j是排序后数组的索引。我们用一个虚拟的索引-1或m来表示基准点 ( O )。为了方便我们可以将基准点 ( O ) 放在排序数组的最前面或最后面但因为它不参与极角排序它是原点所以需要特殊处理。一种常见的实现方式是初始化dp[i][j]为一个二维数组大小为(m1) x (m1)其中索引m代表基准点 ( O )。初始化对于每个点i(0 i m)如果从 ( O ) 到i的线段右侧没有其他点相对于当前基准点集则dp[m][i] 1。这表示一条从 ( O ) 出发到i的路径。转移对于所有i j k如果valid[j][k]为真则dp[j][k] dp[i][j]。统计答案对于所有i j如果valid[j][m]为真即从j闭合回 ( O ) 的边合法则将dp[i][j]加入答案。这里valid[j][m]需要特殊计算表示从点j到基准点 ( O ) 的线段其右侧不能有任何已排序的点即所有点都应在左侧。4.3 复杂度分析与优化预处理valid数组需要 ( O(m^3) ) 的时间因为有三重循环。对于 m 7979^3 ≈ 493,039在可接受范围内。DP转移需要枚举i, j, k也是 ( O(m^3) )。总复杂度对于每个基准点 ( O )需要 ( O(m^3) ) 的时间。共有 N 个基准点所以总复杂度为 ( O(N^4) )。对于 N8080^4 40,960,000大约4千万次运算在C中经过良好实现是可以接受的。注意在实际编码中需要注意使用long long类型存储坐标和叉积避免溢出。同时判断点是否在线段左侧时要使用严格大于号以避免将共线的点误判为在内部。5. 边界情况与常见陷阱5.1 共线点的处理这是本题最容易出错的地方。题目要求凸包内部没有点但边界上呢题目条件“凸包的顶点恰好都是给定点集中的点”意味着如果有一些点共线它们可能都成为凸包的顶点例如所有点都在一条直线上那么凸包就是一条线段两个端点是顶点。但我们的算法通常只寻找面积大于0的凸多边形。如何处理面积为零的凸包线段根据题意两个点组成的点集其凸包是一条线段。它是否有“内部”线段的内部通常被认为是线段上除端点外的部分。如果给定的其他点都在这条线段上那么它们是在边界上而不是内部。题目条件“内部不包含任何其他给定点”是满足的。那么这样的两个点集是否应该被计数这需要仔细审题。在AtCoder官方题解和通常的理解中只计数面积大于0的凸包即至少需要三个不共线的点。因此两个点的集合不计入答案。我们的DP算法自然也不会形成闭合路径因此不会计数。三点共线如果三个点共线它们无法形成一个面积大于0的凸多边形因此也不应被计数。在我们的算法中valid检查要求点严格在线段左侧共线的点叉积为0会导致检查失败从而不会被纳入凸包路径。5.2 点集去重与排序稳定性输入的点可能有重复吗题目通常不会给出重复点但为了鲁棒性可以在读入后去重。如果有重复点它们会导致极角排序时出现相同的点进而引起混乱。在极角排序时如果两个点相对于基准点 ( O ) 的极角相同则按它们与 ( O ) 的距离排序近的在前。这是为了保证在构建凸包时如果多个点共线我们优先选择近的点作为路径上的点实际上对于凸包计数共线的点需要特别小心。如果多个点与 ( O ) 共线它们可能只能有一个作为凸包顶点最远的那个近的点会在凸包内部或边上。我们的valid检查会处理这种情况如果近的点在线段上叉积为0valid会为false从而阻止路径将其作为顶点。5.3 基准点选择与去重如前所述为了避免一个凸包被多次计数我们只在每个凸包“最小”的顶点处计数它。实现时在枚举基准点 ( O ) 后我们只考虑那些在全局坐标系下比 ( O ) “大”的点例如按照(x, y)字典序(x, y) (O.x, O.y)或者更简单的方法在枚举基准点 ( O ) 时只将其他点中那些满足“相对于 ( O ) 的极角大于0”的点纳入DP。同时在初始化dp[m][i] 1时需要检查线段 ( (O, i) ) 的右侧是否有其他点相对于当前点集。如果有则这个初始化就是无效的因为这样的线段不能作为凸包的第一条边。5.4 模运算与答案输出由于答案可能很大通常要求对某个质数如 ( 10^97 ) 取模。在DP过程中每次加法后都要取模。最终答案需要除以2吗不因为我们统计的是每个凸包一次通过基准点去重所以直接输出累加和即可。6. 完整代码框架与测试以下是基于上述思路的C代码框架。请注意为了清晰省略了一些细节和优化。#include bits/stdc.h using namespace std; const int MOD 1e97; 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; } long long cross(const Point a, const Point b) const { return (a - *this).cross(b - *this); } bool operator(const Point p) const { return tie(x, y) tie(p.x, p.y); } bool operator(const Point p) const { return tie(x, y) tie(p.x, p.y); } }; int main() { int N; cin N; vectorPoint pts(N); for (int i 0; i N; i) cin pts[i].x pts[i].y; sort(pts.begin(), pts.end()); // 排序便于去重和基准点选择 pts.erase(unique(pts.begin(), pts.end()), pts.end()); N pts.size(); if (N 3) { cout 0 endl; return 0; } // 少于3个点无法构成凸多边形 long long ans 0; // 枚举每个点作为基准点O for (int o 0; o N; o) { Point O pts[o]; vectorPoint rest; for (int i 0; i N; i) { if (i o) continue; // 可选只保留那些在O“之后”的点用于去重。这里为了简单先全部保留。 rest.push_back(pts[i]); } int m rest.size(); // 按极角排序 sort(rest.begin(), rest.end(), [](const Point a, const Point b) { Point va a - O, vb b - O; long long cross va.cross(vb); if (cross ! 0) return cross 0; // 逆时针排序 return va.x * va.x va.y * va.y vb.x * vb.x vb.y * vb.y; // 距离近的优先 }); // 预处理valid[i][j] vectorvectorbool valid(m, vectorbool(m, false)); for (int i 0; i m; i) { for (int j i1; j m; j) { bool ok true; for (int k i1; k j; k) { if (rest[i].cross(rest[j], rest[k]) 0) { // 非严格左侧 ok false; break; } } valid[i][j] ok; } } // DP数组dp[i][j] 表示最后一条边为 (i, j) 的路径数i,j是rest中的索引 // 为了方便我们使用大小为 (m1) 的数组索引m代表基准点O vectorvectorint dp(m1, vectorint(m1, 0)); // 初始化从O到每个点i的路径 for (int i 0; i m; i) { // 需要检查线段(O, i)的右侧是否有其他点实际上如果右侧有点那么这些点应该具有更小的极角 // 但我们的排序是逆时针的所以右侧的点在排序数组中可能在i之前。我们需要检查。 bool ok true; for (int k 0; k i; k) { if (O.cross(rest[i], rest[k]) 0) { // 如果点k在(O,i)的右侧或共线 ok false; break; } } if (ok) dp[m][i] 1; // 虚拟索引m代表O } // DP转移 for (int i 0; i m; i) { for (int j i1; j m; j) { if (dp[m][i] 0 dp[i][j] 0) continue; // 小优化 for (int k j1; k m; k) { if (valid[j][k]) { dp[j][k] (dp[j][k] dp[i][j]) % MOD; } } } } // 统计答案闭合回O for (int i 0; i m; i) { for (int j i1; j m; j) { if (dp[i][j] 0) continue; // 检查从j闭合到O是否合法线段(j, O)的右侧不能有任何点 bool ok true; for (int k 0; k m; k) { if (k j) continue; if (rest[j].cross(O, rest[k]) 0) { // 注意这里顺序rest[j] - O - rest[k] ok false; break; } } if (ok) { ans (ans dp[i][j]) % MOD; } } } } cout ans endl; return 0; }6.1 测试用例与调试测试时可以从简单情况开始三个点构成一个三角形答案应为1。四个点构成一个凸四边形答案应为1整个四边形加上4个三角形任选3个点共5个。四个点构成一个三角形内部有一个点答案应为1个三角形和3个三角形每个包含内部点的三角形不符合条件所以只有1个。所有点共线答案应为0。在实现时务必注意坐标范围使用long long防止叉积溢出。调试时可以输出中间数组如valid和dp来验证逻辑。7. 算法总结与扩展思考ABC202F Integer Convex Hull 是一道将计算几何与动态规划结合得非常好的题目。它考察了几个关键能力问题转化能力将点集计数转化为凸多边形计数再转化为有序路径计数。几何处理能力熟练运用叉积判断点与线段的位置关系。动态规划状态设计能力在看似需要指数级状态的问题中通过挖掘几何性质设计出多项式复杂度的DP。细节处理能力边界情况共线点、去重、初始化条件等。解决此类问题的一般步骤理解并严格定义问题明确输入输出和约束。思考暴力解法分析其瓶颈。寻找问题中的特殊结构或性质如凸包的有序性、局部性质。设计基于顺序的DP并确定状态表示和转移条件。预处理辅助信息如点对间是否合法。处理边界情况和去重。实现并测试。这道题还可以有变种例如计算凸包面积之和、周长之和等其核心DP框架是相似的。掌握这种“有序DP计数”的思想对于解决许多组合几何问题都大有裨益。在实际编码竞赛中遇到此类题目需要保持冷静一步步分析几何条件将其转化为可处理的约束再套用经典的DP模型。多练习类似的题目才能培养出快速看穿问题本质的直觉。