简介：面向ACM-ICPC等程序设计竞赛的C++模板合辑，聚焦图论、动态规划、计算几何等高频考点，按头文件模板、数学、字符串、数据结构、图论、计算几何、动态规划七大模块分类，收纳快速幂、Dijkstra、KMP、线段树、凸包、LCS等可直接使用的核心代码，既适合赛前集中速刷，也可用于日常算法训练与教学示例。压缩包共83个文件，整体约449KB，主体是65个cpp源码文件，另含LaTeX相关文件与PDF速查手册、Python辅助测试脚本、Makefile构建脚本、开源许可证等，便于本地编译、查阅和二次整理。技术文档与代码分离，CheatSheet可自行生成速查页，src目录下各模块结构鲜明、注释规范，降低检索成本。页面已有29人浏览学习，对希望建立个人算法模板库的竞赛选手而言，是一份轻量但覆盖较全的实用性资源；按主题查阅即可快速定位图论、DP或几何模板。
1. C++竞赛常用算法模板合集：先想清楚自己在攒什么
很多打算法竞赛的朋友都存过一份“C++常用算法模板”，但真正到了赛场上能直接抄起来就用的，往往不是网上整段整段的题解代码，而是你自己整理过、注释过、验证过的一批核心模块。这个合集要解决的，不是“有没有模板”，而是“模板到了关键时刻能不能信得过”——图论里最短路怎么写不会爆栈，动态规划里状态定义怎么不写歪，计算几何里凸包排序的极角序怎么不出精度问题。这篇文章不会给你一份打包下载的文件，而是把一个可复现的模板库拆开：每类模块存什么、参数怎么调、哪些地方最容易翻车，以及我踩过的几个血泪坑。适合想系统整理自己模板库的选手，也适合刚入门、想从“抄代码”过渡到“用代码”的人。
2. 基础数学模板：快速幂、素数筛与 IO 加速三板斧
2.1 快速幂与矩阵快速幂：从 a^b 到斐波那契
快速幂是整套模板库里出现频率最高的模块，因为几乎所有取模运算场景都会用到它。它的核心思路是把指数拆成二进制，用倍增替代循环乘法，把 O(b) 降到 O(log b)。平时我用得最多的版本是带取模的，模数不固定时建议把 mod 作为参数传进去，而不是写成全局变量，这样换题时不用改函数体。
// 快速幂：计算 (base^exp) % mod long long qpow(long long base, long long exp, long long mod) { long long res = 1 % mod; base %= mod; // 先取模，防止后面乘法溢出 while (exp > 0) { if (exp & 1) res = res * base % mod; // 当前位为1时乘入结果 base = base * base % mod; // 底数自身平方 exp >>= 1; // 指数右移一位 } return res; }逻辑在于每次对指数右移判断二进制末位是否为 1，是则累乘当前底数。底数每次都平方，对应二进制位权倍增。参数上要留意三点：一是res初始值写成1 % mod可以兼容 mod=1 的边界；二是所有乘法都要紧跟% mod，中间变量必须用 long long，否则两数相乘直接溢出 int；三是如果指数很大且底数是负数，先把base %= mod转成正的再运算。
矩阵快速幂是同一思想的延伸，常见于斐波那契数列、线性递推加速。模板上只需要重载矩阵乘法，再复用同样的二进制拆分逻辑。我习惯把矩阵封装成一个结构体，矩阵乘法三个循环嵌套时注意内层累加用 long long，最后统一取模。
struct Mat { long long m[2][2]; Mat(bool unit = false) { memset(m, 0, sizeof(m)); if (unit) m[0][0]=m[1][1]=1; } }; Mat mul(const Mat& a, const Mat& b, long long mod) { Mat c; for (int i = 0; i < 2; ++i) for (int k = 0; k < 2; ++k) if (a.m[i][k]) for (int j = 0; j < 2; ++j) c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod; return c; }这里乘法的循环顺序我刻意调成了 i-k-j，先判断a.m[i][k]是否为零，能跳过不少无效计算。矩阵尺寸固定为 2 是因为斐波那契递推矩阵是 2x2，如果题目给的递推阶数更高，把数组开成 N x N 并把循环上界改成变量即可。
2.2 素数筛的两个版本：埃氏筛与线性筛
判断质数这个动作，在竞赛题里从来不是单独出现，而是内嵌在质因数分解、欧拉函数、数论分块等场景里。单点判断质数用试除法就够，O(sqrt(n)) 的写法里注意循环到 sqrt 即可；但如果是区间筛、预处理一批质数，就要用筛法。埃氏筛代码短、易理解，处理 1e6 级别的范围完全够用。
// 埃氏筛：筛出 1..n 的所有质数，isPrime[i]=true 表示 i 为质数 void sieve_eratosthenes(int n, vector<bool>& isPrime, vector<int>& primes) { isPrime.assign(n + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; ++i) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) // 从 i*i 开始，避免重复标记 isPrime[j] = false; } } primes.clear(); for (int i = 2; i <= n; ++i) if (isPrime[i]) primes.push_back(i); }埃氏筛的优化点是从i*i开始标记，因为小于i*i的合数一定被更小的质因子标记过了。如果追求更严格的线性复杂度，可以写欧拉筛：每个合数只被它的最小质因子筛掉一次。差别在 1e7 以上数据量时才明显，普通竞赛 1e6 级别两者时间差可以忽略，我一般先写埃氏筛，毕竟它不容易写错。
欧拉筛的维护要点是i % primes[j] == 0时跳出，这一步保证了最小质因子唯一性。参数上需要额外注意：primes数组会随 n 增大而变长，函数外部的 vector 用引用传入，避免反复拷贝的开销。
// 欧拉筛：线性复杂度，每个合数仅被最小质因子筛一次 void sieve_linear(int n, vector<int>& primes, vector<int>& minPrime) { minPrime.assign(n + 1, 0); primes.clear(); for (int i = 2; i <= n; ++i) { if (minPrime[i] == 0) { // i 是质数 minPrime[i] = i; primes.push_back(i); } for (int j = 0; j < (int)primes.size() && primes[j] <= minPrime[i] && i * primes[j] <= n; ++j) { minPrime[i * primes[j]] = primes[j]; if (i % primes[j] == 0) break; // 保证每个合数只被最小质因子记录 } } }2.3 快读与关闭同步：别让 cin 成为 TLE 元凶
这道题明明算法复杂度没问题却超时，最后发现是输入太慢——这个场景在竞赛里太常见了。默认的 cin/cout 因为要和 C 标准 IO 同步，会做大量额外操作。竞赛环境下ios::sync_with_stdio(false)加上cin.tie(nullptr)能解决大部分输入瓶颈，但如果输入数据超过百万行级别的整数，我建议直接上 fread 快读模板。
// 基于 fread 的整数快读 char buf[1 << 20]; int idx = 0, len = 0; inline char getChar() { if (idx >= len) { len = fread(buf, 1, sizeof(buf), stdin); idx = 0; } return len ? buf[idx++] : EOF; } inline int readInt() { int x = 0, f = 1; char c = getChar(); while (c < '0' || c > '9') { if (c == '-') f = -1; c = getChar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getChar(); } return x * f; }模板里readInt返回值是 int，如果题目数值范围到 1e18 就把类型改成 long long。缓冲区大小 1<<20 也就是 1MB，对常见数据量足够。注意这个模板不支持浮点数，需要读 double 的题建议输入流直接走 cin 或 scanf，不要自己手写浮点解析，容易踩边界。输出端同理，可以用putchar封装一个快速输出，但相比之下输出瓶颈出现频率低很多，先保证输入快读到位。
2.4 二分边界：写对 l 与 r 的三件套
二分看起来简单，实际翻车率奇高，尤其出题人喜欢卡边界。我在模板库里固定存三套二分：找第一个满足条件的下标、找最后一个满足条件的下标、实数二分。三套都遵循同样的不变量约定，避免临场现推。
// 找第一个 >= target 的位置，不存在返回 n int lower_bound_arr(const vector<int>& a, int target) { int l = 0, r = (int)a.size(); // 左闭右开区间 [l, r) while (l < r) { int mid = (l + r) >> 1; if (a[mid] >= target) r = mid; // mid 满足条件，向左收 else l = mid + 1; // mid 不满足，向右逼 } return l; }这套左闭右开写法的好处是返回下标天然兼容end()语义，r初始化为 n 而不是 n-1，当所有元素都小于 target 时返回 n 也不会越界。实数二分则要多加一个迭代次数控制，而不是比较 eps，因为浮点误差在不同量级下表现不稳定，固定跑 60 次二分最稳。
// 实数二分：求单调函数 f(x) 的零点，固定迭代 100 次 double binary_search_real(double l, double r, const function<double(double)>& f) { for (int i = 0; i < 100; ++i) { double mid = (l + r) / 2.0; if (f(mid) > 0) r = mid; else l = mid; } return (l + r) / 2.0; }3. 图论模板：存图方式、最短路、并查集与网络流的取舍
3.1 存图选型：vector 邻接表与链式前向星
图论题的起点是存图。竞赛里最常用的两种：vector 邻接表和链式前向星。vector 邻接表写法直观，适合绝大多数题目；链式前向星则内存连续、遍历速度快，且在某些需要按输入顺序遍历边、或者要反向修改边权的场景（典型如网络流的反向边）里更顺手。我用链式前向星的一个原因在于：网络流的反向边通过异或i ^ 1访问，实现简洁且不容易错。
struct Edge { int to, next; long long w; }; vector<Edge> edges; vector<int> head; void initGraph(int n) { head.assign(n + 1, -1); edges.clear(); } void addEdge(int u, int v, long long w) { edges.push_back({v, head[u], w}); // 新边插到链表头部 head[u] = (int)edges.size() - 1; }next指向同一起点的上一条边在edges数组中的下标，head[u]存的是最新一条边的下标。遍历以 u 为起点的所有边时，从head[u]开始顺着next走。参数方面注意edges数组容量要预留2 * 边数，因为无向图每条边要 add 两次；有向图只要边数次。如果题目边数很大，先edges.reserve()预分配，避免 vector 扩容造成地址变动。
3.2 最短路：Dijkstra 堆优化与 SPFA 的判断
Dijkstra 堆优化是单源最短路的首选，前提是所有边权非负。它的复杂度 O((V+E)logV)，在 1e5 级别的图上可以轻松跑完。模板里我固定用优先队列，因为手写堆虽然常数小，但竞赛中优先队列的正确率更高，优先队列里的 pair 先按距离再按节点排序，注意默认是大顶堆，要传入greater<pair<long long,int>>使其变为小顶堆。
// Dijkstra 堆优化：dist 初始化为 INF，从 src 出发 vector<long long> dijkstra(int n, const vector<vector<pair<int,long long>>>& g, int src) { const long long INF = 4e18; vector<long long> dist(n + 1, INF); priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq; dist[src] = 0; pq.push({0, src}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; // 惰性删除：旧的更差距离直接跳过 for (auto [v, w] : g[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } return dist; }这里有个细节：很多模板喜欢用if (d > dist[u]) continue;，我用的是d != dist[u]，因为在溢出风险受控时，完全相等才说明这是最新入堆的距离，不等则直接跳过。其实两种写法均可，重点在于必须判重，否则复杂度会退化。
SPFA 我平时不主动用，只在检测负环时才写。负环检测的思路是记录每个节点入队次数，超过 n 次即存在负环，因为最短路径包含环时不会超过 n-1 条边。这个写法在随机图上跑得快，但构造数据很容易卡死，没有负权边时一律 Dijkstra，这点要记住。
// SPFA 检测负环：返回 true 表示存在负环 bool spfa_negative_cycle(int n, const vector<vector<pair<int,long long>>>& g) { vector<long long> dist(n + 1, 0); vector<int> inq(n + 1, 0), cnt(n + 1, 0); queue<int> q; for (int i = 1; i <= n; ++i) { q.push(i); inq[i] = 1; } while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = 0; for (auto [v, w] : g[u]) { if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (!inq[v]) { q.push(v); inq[v] = 1; if (++cnt[v] > n) return true; } } } } return false; }3.3 并查集：路径压缩与按秩合并的组合
并查集在竞赛里更多是作为工具型模块嵌入其他算法（最小生成树 Kruskal、离线处理连通性问题）。单独看代码非常简单，但参数选择有讲究：路径压缩能摊平查找，按秩合并能控制树高。两者合用时复杂度接近反阿克曼函数，这是理论上的最优形态；而只做路径压缩不按秩合并，在极端数据下仍有退化风险。
struct DSU { vector<int> parent, rnk; DSU(int n) { parent.resize(n + 1); rnk.assign(n + 1, 0); for (int i=1; i<=n; ++i) parent[i]=i; } int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (rnk[a] < rnk[b]) swap(a, b); parent[b] = a; if (rnk[a] == rnk[b]) ++rnk[a]; } };find里的路径压缩写成了尾递归，编译器通常能优化掉额外栈开销，但如果数据量到 1e6 以上且树深比较极端，可以考虑写成非递归版本。unite的思路是把较矮的树挂到较高的树上，rnk只在两棵树高度相等时才加一。这道模板我建议直接存结构体而不是散装函数，因为竞赛题里并查集常需要多开几组实例，结构体天然支持多个对象。
3.4 Dinic 最大流：一个够用的模板
网络流模板是图论里最长的一块，也是争议最多的——有人用 ISAP，有人用 HLPP，但 Dinic 在 95% 的竞赛题里够用。它的核心是 BFS 分层图 + DFS 多路增广，每次 BFS 后找最短增广路，直到无法继续分层。模板里两个关键优化：当前弧优化（cur数组记住每条边被用到了哪里）和反向边通过异或访问。
struct Dinic { struct Edge { int to, next; long long cap; }; vector<int> head, level, cur; vector<Edge> edges; int n; Dinic(int n_): n(n_) { head.assign(n+1, -1); edges.clear(); } void addEdge(int u, int v, long long cap) { edges.push_back({v, head[u], cap}); head[u] = (int)edges.size() - 1; edges.push_back({u, head[v], 0}); // 反向边容量 0 head[v] = (int)edges.size() - 1; } bool bfs(int s, int t) { level.assign(n+1, -1); queue<int> q; q.push(s); level[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = edges[i].next) { Edge& e = edges[i]; if (e.cap > 0 && level[e.to] == -1) { level[e.to] = level[u] + 1; q.push(e.to); } } } return level[t] != -1; } long long dfs(int u, int t, long long flow) { if (u == t) return flow; for (int& i = cur[u]; i != -1; i = edges[i].next) { Edge& e = edges[i]; if (e.cap > 0 && level[e.to] == level[u] + 1) { long long ret = dfs(e.to, t, min(flow, e.cap)); if (ret) { e.cap -= ret; edges[i ^ 1].cap += ret; return ret; } } } return 0; } long long maxflow(int s, int t) { long long ans = 0; while (bfs(s, t)) { cur = head; // 每次 BFS 后重置当前弧 while (long long f = dfs(s, t, 4e18)) ans += f; } return ans; } };用 Dinic 时有个约定：addEdge成对添加边，正向边和反向边在edges数组里下标必须相邻，这样i ^ 1才能取到反向边。反向边初始容量为 0，增广后加上实际流量。参数上，flow递归传入时会变小，所以 dfs 出口返回的是实际增广的流量，单次 dfs 可能只有一条路径的增量，外部 while 循环反复调用直到本次分层图的流量耗尽。
4. 动态规划模板：背包、LIS 与区间 DP 的代码化方案
4.1 背包问题的三种变体：01 背包、完全背包与分组背包
动态规划里最容易被模板化的就是背包类问题，因为状态定义和转移方程高度固定。01 背包的一维滚动数组写法是基础中的基础：外层枚举物品，内层体积从大到小遍历，保证每个物品只取一次。这个逆序的原因在于一维数组会继承上一层状态，如果正序遍历，当前物品会被多次使用，从而退化成完全背包——这是最经典的边界理解，值得在注释里写明白。
// 01背包：v为体积数组，w为价值数组，V为背包容量 vector<long long> knap01(const vector<int>& v, const vector<int>& w, int V) { vector<long long> dp(V + 1, 0); for (int i = 0; i < (int)v.size(); ++i) for (int j = V; j >= v[i]; --j) // 逆序遍历容量 dp[j] = max(dp[j], dp[j - v[i]] + w[i]); return dp; }完全背包只是把内层循环改成从v[i]到V正序遍历，含义也从“每个物品取一次”变为“每个物品可以取任意次”。这里有个容易忽略的细节：完全背包正序遍历的中间状态dp[j - v[i]]可能已经包含了当前物品，这正是无限取用所要的效果。分组背包则是在物品外层套一个组循环，每组内做一次 01 背包，注意组内不能用滚动数组正序，还是得组内逆序。
// 分组背包：每组选一个物品，group 里存 (体积, 价值) vector<long long> knapGroup(const vector<vector<pair<int,int>>>& groups, int V) { vector<long long> dp(V + 1, 0); for (auto& items : groups) for (int j = V; j >= 0; --j) for (auto [vol, val] : items) if (j >= vol) dp[j] = max(dp[j], dp[j - vol] + val); return dp; }分组背包的容量循环放在物品循环外层，组内物品共享同一个逆序容量状态，这保证了每组最多选择一个物品。如果你在做树形背包（选课问题），需要先 DFS 子树合并 dp 数组，那是另一个更复杂的变体，模板库里单独存档即可。
4.2 LIS 与 LCS：O(nlogn) 模板及拼接细节
最长上升子序列的 O(nlogn) 解法用到了“维护每个长度下末尾元素的最小值”这一贪心思路。具体操作是每次遇到新元素，就在tail数组里找第一个大于等于它的位置并替换。代码短，但边界条件很容易写错，尤其是 lower_bound 还是 upper_bound 的选择——严格上升用 lower_bound，非严格上升用 upper_bound。
// 最长上升子序列长度：严格上升用 lower_bound，非严格用 upper_bound int lisLength(const vector<int>& a) { vector<int> tail; // tail[k] 表示长度为 k+1 的上升子序列的末尾最小值 for (int x : a) { auto it = lower_bound(tail.begin(), tail.end(), x); if (it == tail.end()) tail.push_back(x); else *it = x; } return (int)tail.size(); }注意tail本身不是 LIS 序列，它只保存每个长度下的最优末尾值。如果题目要求输出具体序列，需要额外开一个数组记录每个元素作为末尾时的前驱下标，然后从最后一个补出来的位置回溯。这个回溯代码在竞赛题里出现频率不高，但有备无患。至于 LCS 的 O(nlogn) 做法，只适用于两个序列中一个无重复元素的情况——把 A 序列映射成下标，B 序列按映射转换成新序列后再求 LIS，这招能大幅提速，但映射前要确认元素不重复，否则会出错。
4.3 区间 DP：枚举长度还是枚举端点？断环成链技巧
区间 DP 的固定套路是“枚举区间长度，再枚举起点，最后枚举分割点”。之所以要先枚举长度，是因为转移依赖更短的区间结果，而长度天然保证了无后效性。代码结构高度一致，只需要根据题目修改转移里的合并逻辑。
// 经典石子合并：dp[l][r] 表示合并区间 [l,r] 的最小代价 int mergeStones(const vector<int>& a) { int n = a.size(); vector<int> pre(n + 1, 0); for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + a[i]; vector<vector<int>> dp(n, vector<int>(n, 0x3f3f3f3f)); for (int i = 0; i < n; ++i) dp[i][i] = 0; for (int len = 2; len <= n; ++len) { for (int l = 0; l + len - 1 < n; ++l) { int r = l + len - 1; for (int k = l; k < r; ++k) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + pre[r + 1] - pre[l]); } } return dp[0][n - 1]; }这里的pre前缀和用于快速求区间和，是石头总代价的加速工具。0x3f3f3f3f是常见的“大数”，用来初始化 dp 数组表示未计算状态。如果要处理环状排列的石子，只需要把数组复制一份接在后面，跑 2n 长度的区间 DP，最后取所有长度为 n 的滑动区间的方案最小值——这就是断环成链，是环形 DP 问题的标准解法，模板库里可以单独存一个断环版。
5. 计算几何模板：向量运算、凸包、射线法与旋转卡壳
5.1 向量运算基座：点积、叉积与精度处理
计算几何是所有模块里最容易出精度问题的一类，90% 的翻车都和浮点数比较有关。我处理浮点判断的固定习惯是：定义一个sgn(x)函数，把浮点比较统一转成eps容差内的 -1/0/1 三态输出。所有几何模板都基于这个函数，避免在 if 里直接写==或>。
const double eps = 1e-8; int sgn(double x) { if (fabs(x) < eps) return 0; return x > 0 ? 1 : -1; } struct Point { double x, y; }; double cross(const Point& a, const Point& b, const Point& c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } double dot(const Point& a, const Point& b, const Point& c) { return (b.x - a.x) * (c.x - a.x) + (b.y - a.y) * (c.y - a.y); }叉积cross(a,b,c)的几何含义是向量 ab 与 ac 的有向面积的两倍，正负表示 c 在 ab 的哪一侧。点积dot(a,b,c)返回向量 ab 与 ac 的点积，可以用来判断夹角是锐角、钝角还是直角。参数上，eps的取值在 1e-8 到 1e-10 之间比较安全，太小会把有效浮点误差放大成非零，太大会把本来不同的点判成相同。这套基座建议所有几何模板都依赖它，遇到坐标范围很大的题，再单开一个 long long 版本避免中间量溢出。
5.2 Andrew 凸包：排序扫两遍
凸包算法里 Andrew 单调链比 Graham 扫描更好写，因为它只需要按坐标排序后做两次单调栈扫描，不需要极角排序。整个算法分两步：先把点按 x 坐标升序、x 相同时按 y 升序排序；然后从左到右扫一遍维护下凸壳，从右到左扫一遍维护上凸壳。每次加入新点时，用叉积判断栈顶元素是否该被弹出——叉积小于等于 0 说明出现了顺时针转弯或共线，要弹出。
vector<Point> convexHull(vector<Point> pts) { sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }); int n = pts.size(); vector<Point> hull(2 * n); int k = 0; for (int i = 0; i < n; ++i) { while (k >= 2 && sgn(cross(hull[k-2], hull[k-1], pts[i])) <= 0) --k; hull[k++] = pts[i]; } for (int i = n - 2, t = k + 1; i >= 0; --i) { while (k >= t && sgn(cross(hull[k-2], hull[k-1], pts[i])) <= 0) --k; hull[k++] = pts[i]; } hull.resize(k - 1); return hull; }cross <= 0会把共线点从凸壳上剔除，如果需要保留边界上的所有共线点，把条件改成< 0即可。hull.resize(k - 1)是因为最后一次循环会把起点重复加入一次。返回的 hull 是逆时针顺序。参数上注意：传入pts是值传递，sort 会直接修改它，如果调用处还需要原始点集，记得传拷贝或者调用前自行复制。
5.3 点在多边形内：射线法与边界判定
点在多边形内的经典做法是射线法：从目标点向右水平发出一条射线，统计与多边形边的交点数量。奇数次交点则点在多边形内，偶数次则在外部。难点在于处理三种边界情况：射线穿过顶点、射线与边重合、点落在边上。常见的处理技巧是“忽略水平边”，并在顶点相交时只统计一边的端点。
bool pointInPolygon(const Point& p, const vector<Point>& poly) { int n = poly.size(); bool inside = false; for (int i = 0, j = n - 1; i < n; j = i++) { const Point& a = poly[i], & b = poly[j]; if (sgn(cross(a, b, p)) == 0 && sgn(dot(p, a, b)) <= 0) return true; // 点在边上 if (((a.y > p.y) != (b.y > p.y)) && sgn(p.x - a.x + (p.y - a.y) / (b.y - a.y) * (b.x - a.x)) > 0) inside = !inside; } return inside; }这段代码里((a.y > p.y) != (b.y > p.y))等价于“p 的 y 坐标严格位于 a.y 和 b.y 之间”，这是为了处理射线穿过顶点时只计一次。除法换成叉积形式能减少精度损耗，但直接写法更容易读懂。如果多边形顶点数量巨大且查询次数很多，可以用扫描线预处理，或者用向量叉积判断点是否在凸多边形内——凸多边形只要所有边的叉积方向一致即可判断。
5.4 旋转卡壳：求凸包直径
旋转卡壳解决的问题是“凸包上距离最远的两点”，经典应用是平面最近点对之外的最远点对。它基于一个观察：距离一个顶点最远的点，沿着凸包移动时是单调的，所以可以双指针扫描。
// 旋转卡壳：返回凸包直径的平方（避免浮点误差） long long rotatingCalipers(const vector<Point>& hull) { int n = hull.size(); if (n == 2) { long long dx = hull[1].x - hull[0].x, dy = hull[1].y - hull[0].y; return dx * dx + dy * dy; } long long ans = 0; int j = 1; for (int i = 0; i < n; ++i) { while (sgn(cross(hull[i], hull[(j + 1) % n], hull[(i + 1) % n])) > sgn(cross(hull[i], hull[j], hull[(i + 1) % n]))) j = (j + 1) % n; long long dx = hull[j].x - hull[i].x, dy = hull[j].y - hull[i].y; ans = max(ans, dx * dx + dy * dy); } return ans; }这里返回的是直径的平方，用 long long 规避浮点误差。叉积比较时两边同时过sgn是为了统一量纲，防止不同精度的叉积直接比较。参数上有个细节：j的初始化为 1，循环里(j+1)%n保证指针不会越界。旋转卡壳还衍生了求最小外接矩形、两凸包最近距离等变体，核心都是这个双指针单调移动的思路，模板库里存一份旋转卡壳可以辐射不少题。
6. 模板库实战中的六个典型翻车现象：原因与对策
6.1 快速幂取模结果一直是 0
现象：某题用快速幂算组合数取模，输出恒为 0，但手算小数据没问题。原因：模数不是质数，或者底数和模数不互质时，乘法逆元的预处理出现了问题，快速幂本身没错，错在逆元用了费马小定理——它只对素数模成立。解决：确认模数是否为素数；不是素数时改用扩展欧几里得求逆元，或者用中国剩余定理拆分。这个坑在数论题里出现频率极高，建议在模板库的快速幂注释里直接注明“仅当 mod 为素数时可用逆元”。
6.2 Dijkstra 堆优化空间爆满
现象：1e5 点的图跑最短路直接 MLE，检查后是优先队列里堆积了大量过期状态。原因：没有使用惰性删除，或者每次松弛都 push 一个 pair，旧状态永远不会弹出去，导致堆无限膨胀。解决：确认if (d != dist[u]) continue;的判别在，若用d > dist[u]也成立，但注意两者在数值恰好相等时行为不同。另一个细节是edges的reserve一定要做，vector 扩容的峰值内存很容易超过限制。
6.3 并查集 find 写成了循环后忘却路径压缩
现象：数据量一大就超时，百思不得其解。原因：find函数的路径压缩只发生在递归返回时，如果迭代版本里没有把沿途节点的 parent 直接指向根，整个树不会变矮。解决：检查 find 实现里是否在找到根后回写了 parent。我常用的保险写法是递归版，因为即使编译优化不佳，绝大多数题目数据规模下递归栈深度不会超过树高，而树高在按秩合并下是 log 级别。如果题目构造了故意卡递归的链式数据，把树高打满成线性，则改用非递归版本并显式回写。
6.4 凸包算出来只有两个点
现象：上千个点求凸包，结果 hull 数组只有 2 个元素。原因：所有点共线，或者叉积判断条件写反了，把凹进去的点也弹出了；还有一种可能是排序比较器没处理好 x 相同的情况。解决：先手动检查输入是否包含共线点；cross <= 0是剔除共线点的选择，如果题目要求保留共线点改成< 0；排序比较器改成先 x 再 y 的严格弱序，杜绝比较器返回相等歧义导致 sort 崩溃。这类问题在几何题里叫“数据退化”，出题人经常故意塞这种边界。
6.5 区间 DP 初始化 0x3f3f3f3f 后求最小值取到巨大值
现象：dp 数组大量状态依然是 INF，但正确结果应该存在。原因：枚举分割点时，某个合法的分割点组合提前被剪枝跳过了，或者枚举区间长度时起点写成了 0 而不是 1，导致部分区间从未被计算。解决：在区间 DP 模板里打印中间 dp 状态排查，先确认dp[i][i] = 0的初始化覆盖了全部单点状态，再确认长度循环的下界从 2 开始且l+len-1不越界。很多区间 DP 的代码看起来一致，实际 bug 都在下标偏移上。
6.6 射线法判断点在多边形内部但外部点也进了
现象：用射线法测试几何题数据，部分明显在图形外的点被判定在内部。原因：射线恰好穿过多边形顶点，交了两次交点被误判为偶数，但实际应算作奇数。解决：上面给的模板里(a.y > p.y) != (b.y > p.y)这种写法就是为了规避顶点重复计数问题。如果还出错，检查点是落在边上的判定是否生效——边上的点必须优先返回 true，否则射线法会把它当成外部。
以上六条坑是我在整理模板库过程中反复踩过的。每条最后都落在了具体写法选择上，而不是玄学调参。我的习惯是每踩一次就回模板库补一条注释，把“为什么这么写”写清楚，而不是只留代码。模板的价值不在代码本身，而在你为它做过的所有验证和记录，这个动作比任何现成模板都有用。希望帮到你。
本文还有配套的精品资源，点击获取
