main.tex

\documentclass[a4paper]{ctexbook}
\usepackage[dvipsnames]{xcolor}  % 扩展颜色支持
\usepackage{listings}  % 代码高亮宏包
\usepackage[hidelinks]{hyperref}
\usepackage{graphicx}
\usepackage{caption}   % 控制标题格式 (可选)
\usepackage{float}     % 提供 [H] 固定位置选项 (可选)
\usepackage{amsmath}   % 数学公式支持

\usepackage[
    a4paper,       % 保持纸张类型不变
    left=2.5cm,       % 减小左边距
    right=2.5cm,      % 减小右边距
    top=2.5cm,      % 上边距
    bottom=2.5cm,   % 下边距
    includeheadfoot % 包含页眉页脚在边距内
]{geometry} % 引入页边距控制宏包

% 自定义C++高亮风格
\lstdefinestyle{MyCStyle}{
    % 基础样式
    language=C++,               % 使用C++语法规则(C语言兼容)
    basicstyle=\ttfamily\small, % 基础字体
    backgroundcolor=\color{gray!5}, % 背景色
    frame=single,                % 边框样式
    framesep=3pt,               % 边框内边距
    rulecolor=\color{black!30}, % 边框颜色
    % 行号设置
    numbers=left,               % 左侧行号
    numberstyle=\tiny\color{gray}, % 行号样式
    stepnumber=1,               % 每行显示行号
    numbersep=8pt,              % 行号与代码间距
    % 代码换行
    breaklines=true,            % 自动换行
    % breakatwhitespace=true,     % 只在空格处换行
    postbreak=\mbox{\textcolor{red}{$\hookrightarrow$}\space}, % 换行标记
    tabsize=4,                  % 制表符等效空格数
    showstringspaces=false,     % 字符串中不显示空格
    % 语法高亮颜色定义
    commentstyle=\color{ForestGreen}\itshape, % 注释样式
    keywordstyle=\color{blue}\bfseries,       % 关键字样式
    stringstyle=\color{red},                   % 字符串样式
    directivestyle=\color{purple}\bfseries,    % 预处理指令
    identifierstyle=\color{black},              % 标识符样式
    % 特殊字符高亮
    literate=*                  % 特殊字符处理
        {0}{{{\color{magenta}0}}}1
        {1}{{{\color{magenta}1}}}1
        {2}{{{\color{magenta}2}}}1
        {3}{{{\color{magenta}3}}}1
        {4}{{{\color{magenta}4}}}1
        {5}{{{\color{magenta}5}}}1
        {6}{{{\color{magenta}6}}}1
        {7}{{{\color{magenta}7}}}1
        {8}{{{\color{magenta}8}}}1
        {9}{{{\color{magenta}9}}}1
        {.0}{{{\color{magenta}.0}}}2
        {.1}{{{\color{magenta}.1}}}2
        {.2}{{{\color{magenta}.2}}}2
        {.3}{{{\color{magenta}.3}}}2
        {.4}{{{\color{magenta}.4}}}2
        {.5}{{{\color{magenta}.5}}}2
        {.6}{{{\color{magenta}.6}}}2
        {.7}{{{\color{magenta}.7}}}2
        {.8}{{{\color{magenta}.8}}}2
        {.9}{{{\color{magenta}.9}}}2
}

% C++关键字扩展 (包含C和C++常见关键字)
\lstset{style=MyCStyle,
    morekeywords={  % 添加额外关键字
        alignas, alignof, constexpr, decltype,
        noexcept, nullptr, static\_assert, thread\_local,
        override, final, using, dynamic\_cast,
        const\_cast, reinterpret\_cast, static\_cast,
        template, typename, namespace, explicit,
        inline, noexcept, constinit, consteval,
        concept, requires, co\_await, co\_return,
        co\_yield, char8\_t, char16\_t, char32\_t
    }
}

\begin{document}
\begin{titlepage}
	\centering
	\vspace*{2cm}

	% 封面主图占位符, 可替换为实际图片文件
	% \includegraphics[width=0.5\textwidth]{./blacksimithing.png}\\[1.5cm]

	% 书名与副标题, 中间使用 en-dash
	{\Huge\bfseries 基础算法示例 -- C++实现\par}
	\vspace{2cm}
	% 作者、机构等信息 (可修改) 
	{\Large 作者: Haoming Bai\par}
	\vfill

	% 两个小图占位符
	\begin{figure}[h]
		\centering
		\includegraphics[width=0.6\textwidth]{./ccpc_logo.png}
		% \hspace{1cm}
		% \includegraphics[width=0.2\textwidth]{cover_image3_placeholder}
	\end{figure}
	\vfill

	% 出版日期
	{\large \today\par}
\end{titlepage}

% 目录页
\clearpage
\addcontentsline{toc}{chapter}{目录}
\tableofcontents
\clearpage

% 正文开始
\mainmatter

\chapter{概念}

Concept (概念) 是本 C++ 模板的一项核心概念. "概念"引进于 C++20, 是通过一些限定的组合, 进而约束模板的适用范围, 同时也给代码补全器提供便利. 模板还可以简化报错信息, 将抽象的重载决议简化为条件不满足. 例如在 "Addable" 这个概念出现后, 用户可以知道自己传入的参数类型不满足加法性质, 而不是奇怪地在层层编译器的堆栈展开之后, 发现自己的类型不能满足标准库中的一个奇怪函数. 本章节仅覆盖了最常用的一些基础概念, 一些不够常用的概念会分布在各个章节之中. 在本模板中, 除去AVL树部分由于一些特殊原因, 并未使用概念以外, 所有代码都使用概念进行约束.

\lstinputlisting[language=C++, caption=concepts.cpp, style=MyCStyle]{./concepts.cpp}

\chapter{图论}

图是计算机数据结构中最复杂的结构之一. 图论 (Graph theory) 是数学的一个分支, 图是图论的主要研究对象. 图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形, 这种图形通常用来描述某些事物之间的某种特定关系. 顶点用于代表事物, 连接两顶点的边则用于表示两个事物间具有这种关系.

图分为有向图和无向图, 有向图意味着在一个图中, 所有的边是有方向的. 有向图就像漂流一样, 游客只能顺着水流或者水车, 从水位高的地方去往水位低的地方, 或者从水车从山脚到山顶. 也可以回忆一下高中学到的洋流图, 我至今仍然记得当年学到的, 在南极洲附近的那个西风漂流. 西风漂流应该是只能从西到东, 从东到西就要出事情. 当然, 就像漂流的游客可以从山顶漂到山脚, 也可以从山脚坐水车来到山顶, 在有向图中, 如果存在 A->B, 并不意味着不能存在 B->A. 当然无向图就要简单得多, 就像大多数的城市路网规划一样. 如果你走错了路, 本应该在顾戴路下高架却一路开到了漕宝路, 你也可以原路返回.

这份算法示例中的图全部是有向图, 一些强制需要无向图的算法都是用有向图去模拟的无向图. 因为起草的时间很早, 所以没有使用概念约束, 同时很多算法因为较为常见, 也没来得及编写注释, 还请读者谅解. 不过想到使用这份模板的人算法水平应该远高于我, 所以应该也不需要很详细的解释了.

\lstinputlisting[language=C++, caption=graph.cpp, style=MyCStyle]{./graph.cpp}

\chapter{数据结构}

数据结构是大学计算机专业的第一门专业课, 也是ICPC共同主席, 西北工业大学计算机基础教学中心的副主任姜学锋教授眼中对于算法能力帮助最大的一门课. 常见的在课上会提及的数据结构在 C++ 的标准库中通常都有, 或者存在更好的平替, 那么只要记住 ADT, 然后在编程中使用标准的实现就足够了. 这里关注的是那些不常见的数据结构.

\section{快速排序}

快速排序是 408 课程数据结构中一种非常重要的算法. 快速排序因为比归并排序更少的数据和元素移动而具备更加优秀的速度. 本来排序算法在标准库中已经相当成熟, 但是因为笔者的一位朋友在面试时, 作为陕西省赛的银牌, 在面试中居然没有写出来, 感到十分惭愧. 因此, 窃以为必须维护一个堪用, 易懂的快速排序实现, 不但可以作为算法的参考, 更可以警示后人充分理解 Divide and conqure 的思想, 以及 "枢轴" 的作用.

\lstinputlisting[language=C++, caption=quick\_sort.cpp, style=MyCStyle]{./quick_sort.cpp}

\section{线段树}

线段树是算法竞赛中常用的用来维护区间信息的数据结构. 线段树可以在 $O(\log(N))$ 的时间复杂度内实现单点修改, 区间修改, 区间查询 (区间求和, 求区间最大值, 求区间最小值) 等操作. 线段树存在两种常见的存储方案. 一种是朴素地使用数组存储数据, 然后通过一系列的计算, 维护节点在树中的位置和下标的关系, 这种方法常数小, 但是写起来很复杂, 也不够灵活. 另外一种是使用 "动态开点" 的算法, 使用链式结构的二叉树, 同时使用线性的方法开辟内存空间, 这样就可以简化代码, 同时保证速度. 后一种方案可以把线段树写的很大, 同时可以支持持久化等高阶操作.

\subsection*{朴素线段树}

朴素线段树基于分治思想构建二叉树: 根节点覆盖整个区间, 每个非叶节点递归二分其区间 (左子树 $[l, mid]$, 右子树 $[mid+1, r]$) , 叶节点对应单元素区间. 节点存储区间聚合信息 (如和/最值) , 更新时自底向上回溯修正受影响的节点值, 查询时合并目标区间的分解子区间结果. 其优势在于:
\begin{itemize}
	\item \textbf{高效查询/更新}: 单点更新与区间查询时间复杂度均为 $O(\log n)$
	\item \textbf{结构清晰}: 标准二叉树实现, 逻辑简单易理解
\end{itemize}
主要缺陷包括:
\begin{itemize}
	\item \textbf{区间更新效率低}: 直接更新每个元素需 $O(n \log n)$ 时间
	\item \textbf{空间冗余}: 需 $4N$ 数组存储树结构, 空间复杂度 $O(n)$
\end{itemize}

尽管在正式文件中通常避免附着测试代码, 但为直观展示线段树通过运算符重载实现字符串加法、乘法及最值等聚合功能的灵活性, 此处特别提供了由AI编写的测试类作为补充示例.

\lstinputlisting[language=C++, caption=segment\_tree/simple\_segtree.cpp, style=MyCStyle]{./segment_tree/simple_segtree.cpp}

\section*{可持久化线段树}

与之前介绍的普通线段树不同, 可持久化线段树 (persistent segment tree) 并非在原地修改节点, 而是通过“路径复制”创建一个新的版本, 旧版本仍可保存历史记录. 这意味着每次更新操作仅复制涉及的那条从根到叶的路径节点, 其他未改动的节点被共享使用, 因此可以高效维护多个历史状态, 而普通线段树更新会破坏原结构, 不支持版本回溯.

可持久化线段树常被应用于 "区间第 $K$ 小" 问题: 先对原数组进行离散化, 并为每个前缀 $A[1\dots i]$ 构建一个版本的值域线段树, 每个节点保存该值段在当前前缀下出现的次数. 查询$[l,r]$区间第 $K$ 小, 可视作 $CT[r]–CT[l–1]$ (两版本的减法) 后, 从根节点下行, 查找 $K$ 所在子区间, 从而在 $O(log(n))$ 内得出答案.

至于“主席树” (Chair/Chairman Tree) 这一称呼, 据说其名字源于一位昵称带 "主席" 二字的选手推广此结构, 故后人暂借此称；也有人说是因为其推广者拼音缩写与中国某前国家主席相同, 因此得名. 无论来源如何, 这个名称在中文竞赛圈内被广泛接受, 几乎成了可持久化值域线段树的代名词.

第 $K$ 小数的查询之所以能够高效实现, 关键在于版本树间共享大量节点, 仅针对一个插入或查询路径创建 $O(log n)$ 个新节点, 版本之间的差异小, 既保持了线段树查询的效率, 也支持历史版本的任意访问, 是处理静态区间 $K_{th}$ 问题的经典方案.

\lstinputlisting[language=C++, caption=segment\_tree/persistent\_segtree.cpp, style=MyCStyle]{./segment_tree/persistent_segtree.cpp}

\section{并查集}

并查集 (Disjoint Set Union, DSU) 是一种高效处理集合合并与查询的数据结构, 常用于解决元素分组, 连通性判断等问题. 在算法竞赛中, 它被广泛应用于图论相关题目, 尤其是在处理无向图的连通分量, 最小生成树 (如 Kruskal 算法) 以及等价关系建模中. 例如, 给定若干合并操作与查询操作, 并查集可以在接近常数时间内判断两个元素是否属于同一集合, 极大提升算法效率. 此外, 在图像识别, 网络社群划分, 物理模拟等实际问题中, 并查集也同样展现了其强大的应用价值.

\lstinputlisting[language=C++, caption=dsu.cpp, style=MyCStyle]{./dsu.cpp}

\section{稀疏表}

稀疏表是一种很简单的数据结构, 在特定的题目里面比线段树的解法常数小, 因此还是应该掌握. 稀疏表适用于这样一种场景: 可重复贡献的场景下的反复查询. 稀疏表的查询非常快, 可以达到最坏 $O(1)$ 的量级, 但是稀疏表只能用于那种 $x*x=x$ 的特殊运算, 且不能进行修改.

\lstinputlisting[language=C++, caption=sparce\_table.cpp, style=MyCStyle]{./sparce_table.cpp}

\section{平衡搜索树}

\subsection*{手工实现的B+树}

B+树是一种专为磁盘存储系统优化的多路平衡搜索树, 在现代数据库和文件系统中占据核心地位. 与传统的二叉搜索树不同, B+树通过高度的多路分叉和严格的结构约束, 在维持高效查询性能的同时, 极大地减少了磁盘I/O操作.

B+树的独特设计体现在以下几个关键特性上:

\textbf{多路平衡结构}: 每个节点可以包含多个键值 (通常为数百个) , 形成宽而矮的树形结构. 这种高扇出特性使得即使存储海量数据, 树的高度也维持在很低的水平, 从而保证了稳定的查询效率.

\textbf{数据与索引分离}: 内部节点仅存储键值作为导航索引, 所有实际数据记录都集中在叶子节点层. 这种清晰的职责分离使得索引结构更加紧凑, 能够在内存中缓存更多的索引节点.

\textbf{叶子节点顺序链接}: 所有叶子节点通过双向链表连接成有序序列, 这使得范围查询和全表扫描变得极其高效. 与传统的树结构相比, B+树无需回溯到父节点即可完成顺序访问.

\textbf{稳定的平衡维护}: B+树通过节点分裂与合并来维持平衡, 本实现采用了\textbf{预分裂策略}, 在插入过程中提前检测并处理可能出现的节点溢出, 避免了级联分裂带来的性能波动, 确保了写入操作的稳定性.

在应用层面, B+树凭借其卓越的I/O优化特性, 成为关系型数据库 (如MySQL InnoDB, Oracle) 的标准索引结构, 现代文件系统 (如NTFS, ext4) 也依赖其管理磁盘空间. 此外, 在分布式存储系统和大数据组件中, B+树同样发挥着关键作用.

\lstinputlisting[language=C++, caption=bplus\_tree.cpp, style=MyCStyle]{./bplus_tree.cpp}

\subsection*{AI辅助完成的自平衡二叉搜索树}

AVL树是一种严格自平衡的二叉搜索树. 它通过在普通二叉搜索树的基础上增加额外的平衡信息 (节点高度) 和遵循一组严格的平衡规则 (AVL规则: 任意节点的左右子树高度差绝对值不超过1) , 确保树在动态插入和删除操作后能通过旋转操作自动恢复完美平衡. 这种近乎苛刻的平衡性是其提供最坏情况下高效查询性能的关键保障.

这里提供了一份由我和AI共同完成的AVL树, 可靠性基本有保障, 仅供参考.

\lstinputlisting[language=C++, caption=avl.cpp, style=MyCStyle]{./avl.cpp}

\section{单调队列}
单调队列是一种基于队列的数据结构, 主要的作用是求解固定滑动窗口的最大值/最小值问题. 这种数据结构满足:
\begin{itemize}
	\item 队列内满足单调性
	\item 插入新元素时通过从队尾弹出元素保持单调性
\end{itemize}

本实现还附带了一个滑动窗口最大值的简单实现 (队列单调递减).

\lstinputlisting[language=C++, caption=mono\_queue.cpp, style=MyCStyle]{./mono_queue.cpp}

\section{单调栈}

单调栈和单调队列是同样的原理, 只是和单调队列不同, 它从栈顶弹出元素.

\lstinputlisting[language=C++, caption=mono\_stack.cpp, style=MyCStyle]{./mono_stack.cpp}

\section{二叉堆}

二叉堆是一种基于完全二叉树的数据结构, 它满足堆序性质: 每个节点的值都大于等于或小于等于其子节点的值. 前者称为最大堆 (根节点最大), 后者称为最小堆 (根节点最小). 由于其完全二叉树的特性, 二叉堆通常使用数组实现, 可以高效地支持插入, 删除最大值/最小值等操作, 常用于实现优先队列或堆排序算法. 常见操作的时间复杂度为 $O(log n)$.

\lstinputlisting[language=C++, caption=heap.cpp, style=MyCStyle]{./heap.cpp}

\chapter{散列方法}

如果数据的范围过大, 就需要一些快速方法缩小这个范围. 例如对于1000个自然数-字符串对, 完全可以使用数组存储, 使用下标代表key, 但是如果简单地使用数组, 一旦数据中出现一个1000000000000-"xyz", 那么内存占用就会过大. 这时候, 合适的散列方法就相当重要.

\lstinputlisting[language=C++, caption=hash\_methods.cpp, style=MyCStyle]{./hash_methods.cpp}

\chapter{计算几何}

图形学是计算机的一个重要分支. 在计算机图形学中, 我们常常需要处理图形的构造, 变换与交互, 例如判断两个物体是否相交, 生成可视化模型的边界, 或进行光线追踪渲染. 这些看似图形学的问题, 其背后往往依赖于严密的几何计算逻辑. 计算几何正是处理这类问题的基础学科, 它研究如何通过算法和数据结构来解决几何对象之间的关系与操作, 如求交, 最近点对, 凸包, 半平面交等问题.

计算几何不仅服务于图形学本身, 在机器人路径规划, 地图导航系统, CAD设计, 物理引擎甚至算法竞赛中也发挥着重要作用. 它为图形学提供了强有力的理论与算法支持, 使得我们能以更高效, 更精确的方式处理二维或三维空间中的复杂几何问题.

\section{计算机和的基本方法}

\lstinputlisting[language=C++, caption=geometry.cpp, style=MyCStyle]{./geometry.cpp}

\section{最近点对}

在平面中, 我们经常需要找到两个最近的点. 相比最传统的暴力方法, 即找到所有点对, 并计算出任意两者之间的距离, 一些方法可以大幅度简化计算, 进而有效降低我们的程序的时间复杂度. 本题中, 我们采用了一种分治与合并的方法, 从概率上, 让算法的复杂度降低到 $O(nlog(n))$.

\lstinputlisting[language=C++, caption=nearest\_point\_pair.cpp, style=MyCStyle]{./geometry/nearest_point_pair.cpp}

\section{凸包}
在平面中, 对于一组点, 我们可以找到一个凸多边形, 使得这些点全部在凸多边形的内部或者在凸多边形上, 这样的凸多边形, 就是凸包. 凸包在很多领域都有应用, 包括旋转卡壳等.

\lstinputlisting[language=C++, caption=convex\_hull.cpp, style=MyCStyle]{./geometry/convex_hull.cpp}

\section{旋转卡壳}

旋转卡壳是计算几何中的一个重要部分. 这里笔者提供了一份凸包的直径代码供参考.

\lstinputlisting[language=C++, caption=convex\_diameter\_square.cpp, style=MyCStyle]{./geometry/convex_diameter_square.cpp}

\chapter{字符串}

在计算机系统中, 字符串作为信息的基本载体, 承载着从数据存储到逻辑控制的核心功能. 尤其在类Unix生态中, 诸如\texttt{grep}的文本搜索、\texttt{sed}的流编辑及\texttt{awk}的模式处理等工具, 均构建于高效字符串操作之上, 印证了Knuth「字符串处理是程序设计技术的试金石」的论断.

本章将实现字符串处理中的部分基础算法模板, 涵盖:
\begin{itemize}
	\item 字符串匹配 (单模式/多模式)
	\item 字典树与自动机
\end{itemize}

后续代码模板均以工业级效率为标准设计, 可直接应用于竞赛及工程场景.

\section{模式匹配}

文本模式匹配是信息检索与文本处理的基石, 其效率直接影响搜索引擎响应速度、基因序列分析等关键场景的性能. 以Unix工具链为例, 当\texttt{grep}在GB级日志中检索模式时, 朴素匹配$O(nm)$的时间复杂度将导致灾难性延迟.

本节实现Knuth-Morris-Pratt(KMP)算法模板, 其核心在于:
\begin{itemize}
	\item 通过\textbf{失配函数}预处理模式串($O(m)$)
	\item 实现$O(n)$时间复杂度匹配
	\item 避免回溯的\textbf{状态机跳转}机制
\end{itemize}
代码设计支持动态模式更新与流式数据匹配, 可直接集成至文本处理系统.

\lstinputlisting[language=C++, caption=kmp.cpp, style=MyCStyle]{./str/kmp.cpp}

\section{字典树}

字典树 (Trie) 作为高效处理字符串集合的树形数据结构, 在搜索引擎自动补全、拼写检查及路由协议中具有不可替代性. 其核心优势在于:
\begin{itemize}
	\item \textbf{前缀共享}: 具有公共前缀的字符串共享存储路径
	\item \textbf{检索加速}: $O(L)$时间完成键查询 ($L$为键长)
	\item \textbf{字典序遍历}: 天然支持按字典序访问所有键
\end{itemize}

本节实现基于数组的双版本Trie模板, 部分支持字符串的删除.

\lstinputlisting[language=C++, caption=trie.cpp, style=MyCStyle]{./str/trie.cpp}

\section{AC自动机}

AC自动机 (Aho-Corasick automaton) 是一种高效的多模式匹配算法, 用于在文本中同时查找多个关键词的出现位置. 其核心结构基于\textbf{Trie树}, 并通过添加\textbf{失败指针} (failure links) 实现快速状态转移.
当匹配失败时, 算法沿失败指针回溯, 避免重复比较, 保证$O(n+m+z)$的时间复杂度 ($n$为文本长度, $m$为模式串总长, $z$为匹配次数). 该算法广泛应用于敏感词过滤, 生物序列分析等领域.

\lstinputlisting[language=C++, caption=aho\_corasick.cpp, style=MyCStyle]{./str/aho_corasick.cpp}

\section{后缀数组}

后缀数组(\textit{Suffix Array, SA})是一种存储字符串所有后缀按字典序排列索引的数据结构. 给定长度为$n$的字符串$S$, 其对应的后缀数组$SA[i]$表示字典序第$i$小的后缀起始下标. 该结构在生物信息学中用于DNA序列快速比对 (如BLAST工具), 在数据压缩中支撑Burrows-Wheeler变换 (BZIP2核心), 并在全文搜索引擎中实现高效的子串匹配 (如Lucene库).

SA-IS算法是一种线性时间构建后缀数组的诱导排序算法. 其核心思想是:
\begin{enumerate}
	\item \textbf{分类}: 将字符分为\textbf{L型} (字典序大于后继) 和\textbf{S型} (小于或等于后继), 标记特殊\textbf{SMS型}子串.
	\item \textbf{递归}: 提取SMS型子串并递归生成子串后缀数组.
	\item \textbf{诱导}: 通过子串SA诱导排序L型后缀,再进一步诱导排序S型后缀.
\end{enumerate}
该算法时间复杂度为$O(n)$, 空间效率优于后缀树, 适用于大规模文本处理 (如基因组序列分析).

\lstinputlisting[language=C++, caption=suffix\_array.cpp, style=MyCStyle]{./str/suffix_array.cpp}

\section{最长回文子串}

最长回文子串问题是指: 在一个字符串中寻找其中最长的对称子串. 换句话说, 这个子串正着读和反着读完全相同.

对于最长回文子串问题, 一种朴素的解法是枚举中心并向两边扩展, 或者使用其它动态规划的方法, 但是这些方式在字符串较长时往往会遇到效率瓶颈.

Manacher算法是一种在线性时间内解决最长回文子串的算法. 它通过在原始字符串中插入分隔符并利用回文的对称性, 避免了重复计算, 将复杂度降低到$O(n)$. 这种高效性使得它不仅是理论研究的成果, 也在一些实际场景中得到了应用. 例如, 在DNA序列分析中寻找对称片段, 在自然语言处理里发现对称的语言结构, 以及在数据压缩中利用回文模式进行优化等.

\lstinputlisting[language=C++, caption=manacher.cpp, style=MyCStyle]{./str/manacher.cpp}

\chapter{数值方法}

在生产实践中, 尤其是大型工业软件的开发过程中, 数值计算的速度和精度通常和软件的运行效率息息相关. 在数学建模, 仿真, 有限元分析等领域, 使用精度高, 效率高的算法通常可以使程序的性能, 比使用低效算法的相同程序提升十倍甚至百倍. 而在生产环境, 微不足道的浮点误差可以造成惨重的人员和财产损失. 由此观之, 在建设中国式现代化的过程中, 为了解决工业软件领域的 "卡脖子" 难题, 提升数值计算的效率是非常重要的一环. 而掌握正确的计算方法, 则是每一位立志成为 "总师型人才" 的计算机专业学生的必修课. 下面笔者将提供一些简单常用的数值计算方法的实现以供参考, 所有代码都配备详尽注释, 力求通俗易懂, 方便移植改造.

\section{辛普森法}

辛普森法是一种常用的数值积分方法, 它的原理是利用二次插值多项式在小区间上近似被积函数, 从而得到定积分的近似值.

然而, 当积分区间较大或被积函数变化复杂时, 单一的辛普森公式往往难以保证精度. 为此, 可以采用复化辛普森法: 将积分区间划分为若干个小区间, 在每个小区间分别应用辛普森公式, 然后将结果加总.这样虽然提高了精度, 但由于分块数目固定, 可能会在函数比较平滑的区间上产生不必要的计算.

自适应辛普森法则通过递归的方式在尽可能少分块的前提下保证精度. 它先在整个区间上应用一次辛普森公式, 再将区间一分为二分别应用辛普森公式, 并比较两者结果.如果二者差异超过误差容许范围, 就继续对子区间递归分裂; 否则接受结果.这样, 自适应辛普森法能够在函数平滑的区域少分块, 在函数变化剧烈的区域多分块, 从而兼顾效率和精度.

在现实应用中, 辛普森法和自适应辛普森法被广泛用于工程与科学计算. 例如, 在航天工程中进行复杂气动力模型的积分估算, 在医学成像中计算复杂函数的积分, 或在金融工程中估算涉及不规则函数的积分问题.

\lstinputlisting[language=C++, caption=asr.cpp, style=MyCStyle]{./numeric/asr.cpp}

\section{快速傅里叶变换}

快速傅里叶变换 (FFT) 是一种高效计算离散傅里叶变换 (DFT) 的算法. 它的主要作用是将信号从时域转换到频域, 从而便于分析信号的频率成分. FFT显著降低了计算复杂度, 从$O(n^2)$降至$O(n \log n)$, 因此在信号处理, 图像处理, 音频分析和数据压缩等领域得到广泛应用.

\lstinputlisting[language=C++, caption=asr.cpp, style=MyCStyle]{./numeric/fft.cpp}

\chapter{压缩版算法}

本章提供各算法的精简模板, 适用于竞赛快速编写. 所有代码均无注释, 请仔细阅读以下使用说明. compact 目录中的代码与普通代码分离, 统一放在 \texttt{compact/} 目录下.

\section{使用须知}

\begin{itemize}
	\item 所有下标均为 \textbf{0-indexed} (与 STL 统一)
	\item compact 版本只考虑简单情况, 不支持复杂泛型
	\item 计算几何统一使用 \texttt{double} 类型
	\item 所有代码均无注释, 接口说明请阅读本章
\end{itemize}

\section{数据结构}

\subsection{线段树}

\texttt{compact/segtree.cpp} 提供基于加法的线段树, 支持区间增量更新和区间求和查询.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{SegTree<T> st(n, zero)} — 构造大小为 $n$ 的空线段树, \texttt{zero} 为加法幺元 (默认为 \texttt{T\{\}})
	\item \texttt{SegTree<T> st(arr, zero)} — 从容器 \texttt{arr} 构造线段树
	\item \texttt{st.update(l, r, diff)} — 区间 $[l, r]$ 每个元素增加 \texttt{diff} (0-indexed, 闭区间)
	\item \texttt{st.query(l, r)} — 查询区间 $[l, r]$ 的和
\end{itemize}

\textbf{注意事项:} \texttt{update} 是增量更新而非赋值. 如需将位置 $i$ 设为 $v$, 应先查询当前值再计算差值. 类型 \texttt{T} 需支持加法、乘 \texttt{size\_t} (用于懒标记累加).

\lstinputlisting[language=C++, caption=compact/segtree.cpp, style=MyCStyle]{./compact/segtree.cpp}

\subsection{主席树 (可持久化线段树)}

\texttt{compact/persistent\_segtree.cpp} 提供两种可持久化线段树: \texttt{PersistentSegTree} (通用权值线段树) 和 \texttt{KthTree} (区间第 $K$ 小).

\textbf{PersistentSegTree 接口:}
\begin{itemize}
	\item \texttt{PersistentSegTree pst(n)} — 构造值域为 $[0, n-1]$ 的空树
	\item \texttt{pst.add(pos, val)} — 在位置 \texttt{pos} 增加 \texttt{val}, 创建新版本
	\item \texttt{pst.query(ver\_l, ver\_r, ql, qr)} — 查询版本 \texttt{ver\_l} 到 \texttt{ver\_r} 之间, 值域 $[ql, qr]$ 的和
\end{itemize}

\textbf{KthTree 接口 (区间第 $K$ 小):}
\begin{itemize}
	\item \texttt{KthTree kt(max\_val)} — 构造值域为 $[0, \text{max\_val}]$ 的空树
	\item \texttt{kt.add(val)} — 插入值 \texttt{val}, 创建新版本
	\item \texttt{kt.kth(l, r, k)} — 查询原数组区间 $[l, r]$ 中第 $k$ 小的值 (0-indexed, $k$ 从 0 开始)
\end{itemize}

\textbf{注意事项:} \texttt{KthTree} 的 \texttt{kth(l, r, k)} 中 $l, r$ 是原数组下标 (0-indexed), $k=0$ 表示最小值. 使用前需先对原数组离散化.

\lstinputlisting[language=C++, caption=compact/persistent\_segtree.cpp, style=MyCStyle]{./compact/persistent_segtree.cpp}

\subsection{AVL树}

\texttt{compact/avl.cpp} 提供自平衡二叉搜索树, 支持插入、删除、排名查询、第 $K$ 大查询、前驱后继.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{AVLTree<T> tree} — 构造空树 (默认 \texttt{std::less<T>})
	\item \texttt{tree.insert(v)} — 插入值 $v$ (支持重复)
	\item \texttt{tree.remove(v)} — 删除一个值 $v$
	\item \texttt{tree.contains(v)} — 查询 $v$ 是否存在
	\item \texttt{tree.count(v)} — 查询 $v$ 的出现次数 (重复元素计数)
	\item \texttt{tree.rank(v)} — 查询 $v$ 的排名 (从 1 开始, 即比 $v$ 小的元素个数 + 1)
	\item \texttt{tree.kth(k)} — 查询第 $k$ 小的元素 ($k$ 从 1 开始)
	\item \texttt{tree.pred(v)} — 查询 $v$ 的前驱 (小于 $v$ 的最大值), 返回 \texttt{std::optional<T>}
	\item \texttt{tree.succ(v)} — 查询 $v$ 的后继 (大于 $v$ 的最小值), 返回 \texttt{std::optional<T>}
	\item \texttt{tree.size()} — 返回元素总数 (含重复)
	\item \texttt{tree.empty()} — 是否为空
\end{itemize}

\textbf{注意事项:} \texttt{rank} 和 \texttt{kth} 的起始值不同: \texttt{rank} 返回从 1 开始的排名, \texttt{kth} 接受从 1 开始的排名. 重复元素会被计数.

\lstinputlisting[language=C++, caption=compact/avl.cpp, style=MyCStyle]{./compact/avl.cpp}

\subsection{稀疏表}

\texttt{compact/st\_table.cpp} 提供静态区间查询的稀疏表, 适用于可重复贡献运算 (如 max, min, gcd).

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{SparseTable<T> st(arr)} — 从容器构造, 默认运算为 \texttt{std::max}
	\item \texttt{SparseTable<T> st(arr, op)} — 指定运算 \texttt{op} (如 \texttt{[](T a, T b)\{return std::min(a,b);\}})
	\item \texttt{st.query(l, r)} — 查询区间 $[l, r]$ 的运算结果 (0-indexed, 闭区间)
\end{itemize}

\textbf{注意事项:} 运算必须满足 $f(x, x) = x$ (可重复贡献) 和结合律. 不支持修改操作. 预处理 $O(n \log n)$, 查询 $O(1)$.

\lstinputlisting[language=C++, caption=compact/st\_table.cpp, style=MyCStyle]{./compact/st_table.cpp}

\subsection{二叉堆}

\texttt{compact/heap.cpp} 提供二叉堆, 支持最大堆和最小堆.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{Heap<T, Compare> heap} — 构造空堆. \texttt{Compare} 默认为 \texttt{std::less<T>} (最大堆). 使用 \texttt{std::greater<T>} 得到最小堆
	\item \texttt{heap.push(val)} — 插入元素
	\item \texttt{heap.pop()} — 弹出堆顶并返回
	\item \texttt{heap.top()} — 查看堆顶 (不弹出)
	\item \texttt{heap.empty()} — 是否为空
	\item \texttt{heap.size()} — 元素个数
\end{itemize}

\textbf{注意事项:} 与 \texttt{std::priority\_queue} 的比较器语义一致: \texttt{std::less} 产生最大堆, \texttt{std::greater} 产生最小堆.

\lstinputlisting[language=C++, caption=compact/heap.cpp, style=MyCStyle]{./compact/heap.cpp}

\subsection{单调队列}

\texttt{compact/mono\_queue.cpp} 提供单调队列和滑动窗口最值函数.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{MonoQueue<T, Compare> mq} — 构造单调队列. \texttt{std::less} 为单调递增 (队首最小), \texttt{std::greater} 为单调递减 (队首最大)
	\item \texttt{mq.push(val, idx)} — 推入元素及其下标
	\item \texttt{mq.pop(idx)} — 如果队首下标等于 \texttt{idx} 则弹出
	\item \texttt{mq.front()} — 获取队首元素
	\item \texttt{slidingWindowMax(a, k)} — 返回数组 \texttt{a} 的滑动窗口最大值 (窗口大小 $k$)
	\item \texttt{slidingWindowMin(a, k)} — 返回数组 \texttt{a} 的滑动窗口最小值
\end{itemize}

\textbf{注意事项:} \texttt{push} 需要传入下标, \texttt{pop} 通过下标判断是否需要弹出队首. 滑动窗口函数返回 \texttt{std::vector<T>}.

\lstinputlisting[language=C++, caption=compact/mono\_queue.cpp, style=MyCStyle]{./compact/mono_queue.cpp}

\section{图论}

\texttt{compact/graph.cpp} 提供有向图的 Dijkstra 最短路、DSU 并查集和 Kruskal 最小生成树.

\textbf{DSU 接口:}
\begin{itemize}
	\item \texttt{DSU dsu(n)} — 构造 $n$ 个元素的并查集 (0-indexed)
	\item \texttt{dsu.find(x)} — 查找 $x$ 的根 (路径压缩)
	\item \texttt{dsu.unite(a, b)} — 合并 $a$ 和 $b$ 所在集合 (按大小合并)
	\item \texttt{dsu.same(a, b)} — 判断 $a$ 和 $b$ 是否在同一集合
\end{itemize}

\textbf{Graph 接口:}
\begin{itemize}
	\item \texttt{Graph g(n)} — 构造 $n$ 个顶点的有向图 (0-indexed)
	\item \texttt{g.addEdge(u, v, w)} — 添加有向边 $u \to v$, 权值 $w$ (类型为 \texttt{long long})
	\item \texttt{g.dijkstra(s)} — 从起点 $s$ 运行 Dijkstra, 返回 \texttt{vector<long long>} 距离数组. 不可达为 $10^{18}$
\end{itemize}

\textbf{Kruskal 接口:}
\begin{itemize}
	\item \texttt{kruskal(edges, n)} — 对边集 \texttt{edges} 运行 Kruskal, 返回 MST 的边集. \texttt{n} 为顶点数
	\item \texttt{KruskalEdge\{u, v, w\}} — 边的结构体, \texttt{u, v} 为端点 (0-indexed), \texttt{w} 为权值
\end{itemize}

\textbf{注意事项:} Dijkstra 使用优先队列优化, 复杂度 $O((V+E) \log V)$. 边权必须非负. Kruskal 返回的边按权值从小到大排序.

\lstinputlisting[language=C++, caption=compact/graph.cpp, style=MyCStyle]{./compact/graph.cpp}

\section{字符串}

\subsection{字典树}

\texttt{compact/trie.cpp} 提供基于数组的字典树, 默认小写英文字母.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{Trie<START, ALPH> trie} — 构造字典树. \texttt{START} 为字母表起始字符 (默认 \texttt{'a'}), \texttt{ALPH} 为字母表大小 (默认 26)
	\item \texttt{trie.insert(s)} — 插入字符串 \texttt{s}
	\item \texttt{trie.count(s)} — 查询字符串 \texttt{s} 的出现次数
	\item \texttt{trie.contains(s)} — 查询字符串 \texttt{s} 是否存在
	\item \texttt{trie.hasPrefix(s)} — 查询是否存在以 \texttt{s} 为前缀的字符串
\end{itemize}

\textbf{注意事项:} 字符串中的字符必须在字母表范围内 (即 \texttt{START} 到 \texttt{START + ALPH - 1}).

\lstinputlisting[language=C++, caption=compact/trie.cpp, style=MyCStyle]{./compact/trie.cpp}

\subsection{AC自动机}

\texttt{compact/aho\_corasick.cpp} 提供两个版本, 请根据场景选择, 避免 MLE.

\textbf{AhoCorasick (DFA + output 合并版):} 在 \texttt{build()} 时将 fail 链上的 output 合并到每个节点, 匹配时直接遍历 output 数组. 适合需要获取每个匹配的\textbf{具体位置}的场景. 缺点是模式串较多时 output 数组可能占用大量内存.

\begin{itemize}
	\item \texttt{AhoCorasick<START, ALPH> ac} — 构造 AC 自动机
	\item \texttt{ac.add(s)} — 添加模式串, 返回 ID (从 0 开始)
	\item \texttt{ac.build()} — 构建 DFA 和合并 output (匹配前必须调用)
	\item \texttt{ac.matchAll(text)} — 返回所有匹配 \texttt{vector<Match>}, \texttt{Match\{pid, pos\}} 为模式串 ID 和起始位置 (0-indexed)
\end{itemize}

\textbf{AhoCorasickTopo (拓扑优化版):} \textbf{不合并 output}, 只记录每个模式串的结束节点. 匹配时跑 DFA 统计节点访问次数, 再按 fail 树的拓扑序从叶到根传播计数. 空间开销远小于 DFA 版, 适合\textbf{只统计出现次数}且模式串很多的场景.

\begin{itemize}
	\item \texttt{AhoCorasickTopo<START, ALPH> ac} — 构造拓扑优化版 AC 自动机
	\item \texttt{ac.add(s)} — 添加模式串, 返回 ID
	\item \texttt{ac.build()} — 构建 DFA 和拓扑序
	\item \texttt{ac.count(text)} — 返回 \texttt{vector<long long>}, 每个模式串的出现次数
\end{itemize}

\textbf{注意事项:} 需要找匹配位置用 \texttt{AhoCorasick}, 只需统计次数用 \texttt{AhoCorasickTopo} (省空间). 两者字母表默认均为小写英文.

\lstinputlisting[language=C++, caption=compact/aho\_corasick.cpp, style=MyCStyle]{./compact/aho_corasick.cpp}

\subsection{后缀数组}

\texttt{compact/suffix\_array.cpp} 提供 $O(n \log^2 n)$ 的后缀数组和 LCP 数组构建.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{suffixArray(s)} — 返回字符串 \texttt{s} 的后缀数组 (0-indexed)
	\item \texttt{lcpArray(s, sa)} — 返回 LCP 数组, \texttt{lcp[i]} 为 \texttt{sa[i]} 和 \texttt{sa[i+1]} 的最长公共前缀长度
\end{itemize}

\textbf{注意事项:} 使用倍增算法, 复杂度 $O(n \log^2 n)$. 返回的 SA 中 \texttt{sa[i]} 表示字典序第 $i$ 小的后缀的起始位置.

\lstinputlisting[language=C++, caption=compact/suffix\_array.cpp, style=MyCStyle]{./compact/suffix_array.cpp}

\subsection{Manacher 算法}

\texttt{compact/manacher.cpp} 提供线性时间最长回文子串算法.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{manacher(s)} — 返回 \texttt{ManacherResult\{start, len\}}, 表示最长回文子串从位置 \texttt{start} 开始, 长度为 \texttt{len} (0-indexed)
\end{itemize}

\textbf{注意事项:} 如果有多个最长回文子串, 返回最先出现的那个. 使用插入分隔符的统一写法, 同时处理奇数和偶数长度回文.

\lstinputlisting[language=C++, caption=compact/manacher.cpp, style=MyCStyle]{./compact/manacher.cpp}

\section{数值方法}

\subsection{快速傅里叶变换}

\texttt{compact/fft.cpp} 提供 FFT 和多项式乘法.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{fft(a, invert)} — 对复数向量 \texttt{a} 进行 FFT. \texttt{invert=false} 为正变换, \texttt{true} 为逆变换. 结果原地修改. 向量大小必须是 2 的幂
	\item \texttt{multiply(a, b)} — 多项式乘法, \texttt{a} 和 \texttt{b} 为系数向量 (\texttt{a[i]} 为 $x^i$ 的系数), 返回结果系数向量
\end{itemize}

\textbf{注意事项:} 使用 \texttt{double} 精度, 对于大系数可能有精度误差. \texttt{multiply} 返回的向量长度会补齐到 2 的幂, 尾部可能有多余的 0.

\lstinputlisting[language=C++, caption=compact/fft.cpp, style=MyCStyle]{./compact/fft.cpp}

\subsection{离散化}

\texttt{compact/discretization.cpp} 提供离散化工具, 将大范围稀疏值映射为紧凑连续下标.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{Discretization d(arr)} — 从容器 \texttt{arr} 构造离散化映射
	\item \texttt{d.hash(v)} — 将原值 $v$ 映射为离散化后的下标 (0-indexed). 不存在返回 -1
	\item \texttt{d.dehash(idx)} — 将离散化下标还原为原值
	\item \texttt{d.size()} — 返回去重后的元素个数
\end{itemize}

\textbf{注意事项:} 构造时自动排序和去重. \texttt{hash} 使用二分查找, 复杂度 $O(\log n)$.

\lstinputlisting[language=C++, caption=compact/discretization.cpp, style=MyCStyle]{./compact/discretization.cpp}

\section{计算几何}

计算几何部分统一使用 \texttt{double} 类型, 各文件之间存在依赖关系. 使用时按依赖顺序 include 即可.

\textbf{依赖关系:}
\begin{itemize}
	\item \texttt{geometry\_point.cpp} — 无依赖, 提供点和向量基础运算
	\item \texttt{geometry\_line.cpp} — 依赖 \texttt{geometry\_point.cpp}, 提供直线和线段
	\item \texttt{geometry\_polygon.cpp} — 依赖 \texttt{geometry\_line.cpp}, 提供多边形运算
	\item \texttt{convex\_hull.cpp} — 依赖 \texttt{geometry\_point.cpp}, 提供凸包
	\item \texttt{nearest\_point\_pair.cpp} — 依赖 \texttt{geometry\_point.cpp}, 提供最近点对
	\item \texttt{convex\_diameter.cpp} — 依赖 \texttt{geometry\_point.cpp}, 提供旋转卡壳
\end{itemize}

\subsection{点和向量}

\texttt{compact/geometry\_point.cpp} 提供二维点和向量.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{Point(x, y)} — 构造点/向量
	\item 运算符: \texttt{+, -, *, /} (向量加减、数乘、数除)
	\item \texttt{a.dot(b)} — 点积
	\item \texttt{a.cross(b)} — 叉积
	\item \texttt{a.len()} — 模长
	\item \texttt{a.len2()} — 模长平方
	\item \texttt{a.dist(b)} — 两点距离
	\item \texttt{a.unit()} — 单位向量
	\item \texttt{a.normal()} — 法向量 (逆时针旋转 90°)
	\item \texttt{a.rotate(rad)} — 逆时针旋转 \texttt{rad} 弧度
	\item \texttt{a.angle()} — 向量与 x 轴夹角 (弧度, $[-\pi, \pi]$)
	\item \texttt{cross(a, b, c)} — 向量 $\vec{ab} \times \vec{ac}$ 的叉积值
	\item \texttt{sgn(x)} — 符号函数, $|x| < \text{EPS}$ 返回 0
\end{itemize}

\textbf{注意事项:} \texttt{EPS = 1e-8}. 比较浮点数时使用 \texttt{sgn} 而非直接比较.

\lstinputlisting[language=C++, caption=compact/geometry\_point.cpp, style=MyCStyle]{./compact/geometry_point.cpp}

\subsection{直线和线段}

\texttt{compact/geometry\_line.cpp} 提供直线和线段运算.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{Line(p1, p2)} — 用两点构造直线
	\item \texttt{Segment(p1, p2)} — 用两点构造线段
	\item \texttt{parallel(l1, l2)} — 判断两直线是否平行
	\item \texttt{lineIntersect(l1, l2)} — 求两直线交点 (需确保不平行)
	\item \texttt{pointToLine(p, l)} — 点到直线距离
	\item \texttt{pointToSegment(p, s)} — 点到线段距离
	\item \texttt{onSegment(p, s)} — 判断点是否在线段上
	\item \texttt{segmentsIntersect(a, b)} — 判断两线段是否相交
	\item \texttt{project(p, l)} — 点在直线上的投影
\end{itemize}

\lstinputlisting[language=C++, caption=compact/geometry\_line.cpp, style=MyCStyle]{./compact/geometry_line.cpp}

\subsection{多边形}

\texttt{compact/geometry\_polygon.cpp} 提供多边形运算.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{polygonArea(p)} — 计算多边形面积 (顶点按顺序排列)
	\item \texttt{inPolygon(pt, p)} — 判断点是否在多边形内 (射线法, 边界上返回 true)
	\item \texttt{polygonCentroid(p)} — 计算多边形重心
\end{itemize}

\lstinputlisting[language=C++, caption=compact/geometry\_polygon.cpp, style=MyCStyle]{./compact/geometry_polygon.cpp}

\subsection{凸包}

\texttt{compact/convex\_hull.cpp} 提供 Andrew 单调链算法.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{convexHull(pts)} — 输入点集, 返回凸包顶点 (逆时针顺序, 不含重复端点)
\end{itemize}

\textbf{注意事项:} 会修改输入点集 (排序和去重). 返回的凸包顶点按逆时针排列. 共线点只保留端点.

\lstinputlisting[language=C++, caption=compact/convex\_hull.cpp, style=MyCStyle]{./compact/convex_hull.cpp}

\subsection{最近点对}

\texttt{compact/nearest\_point\_pair.cpp} 提供分治法最近点对.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{nearestPointPair(pts)} — 输入点集, 返回最近点对的距离
\end{itemize}

\textbf{注意事项:} 会修改输入点集 (排序). 复杂度 $O(n \log n)$. 点数少于 2 时返回无穷大.

\lstinputlisting[language=C++, caption=compact/nearest\_point\_pair.cpp, style=MyCStyle]{./compact/nearest_point_pair.cpp}

\subsection{旋转卡壳}

\texttt{compact/convex\_diameter.cpp} 提供旋转卡壳求凸包直径.

\textbf{接口说明:}
\begin{itemize}
	\item \texttt{convexDiameter(ch)} — 输入凸包顶点 (逆时针), 返回直径 (最远点对距离)
	\item \texttt{convexDiameterSquare(ch)} — 同上, 返回直径的平方 (避免开根号)
\end{itemize}

\textbf{注意事项:} 输入必须是凸包 (逆时针顺序). 复杂度 $O(n)$.

\lstinputlisting[language=C++, caption=compact/convex\_diameter.cpp, style=MyCStyle]{./compact/convex_diameter.cpp}

\end{document}