天津大学ACM竞赛学习笔记：图论、计算几何与数学精华

"这是一份来自天津大学的ACM学习笔记，包含了丰富的算法和数据结构模板，主要使用C++编程语言，并辅以少量Java代码。笔记涵盖了图论、计算几何、数学、数据结构等多个核心领域，是学习和准备ACM竞赛的宝贵资料。" 在图论部分，笔记详细介绍了各种概念和算法，如割点和割边的定义，Kruskal算法用于构建最小生成树，以及树的分治策略。同时，还讲解了第K短路的计算、一般图的匹配问题，如 Dinic 最大流算法、Sap 最大流算法和EK最大流算法。此外，还包括混合图的欧拉回路、最大权闭合图、最大密度子图、最小边割集、二分图最小权覆盖集、最优比例生成树、最小限度生成树、次小生成树、生成树计数、图的十字匹配、树中删除最少边形成n连通集、最短路及其次短路的计算，以及树的最小点覆盖等问题。 计算几何领域，笔记涵盖了基础公式和常用计算几何库的使用，例如处理三角形的各种操作，如计算面积和找到最大面积的三角形。还有凸包的构造，包括两凸包的最短距离、凸包的直径、最大内切圆、三维凸包、半平面交、平面最远点对、网格问题、圆的运算、两圆交的面积、最小圆覆盖、单位圆覆盖最多点、最小球覆盖、圆和多边形的交、直线的反射、扇形的重心、矩形交面积、点在三角形内部的数量、Pick公式求面积、共线最多的点的个数、线段围成的区域储水量、最多正方形个数的计算、最多确定互不平行直线的方法、三角形全等的判断、多边形核的求解以及点的旋转等。 数学部分涉及多种理论和算法，如定理与定义、公式与序列、排列与组合的计算，线性筛法用于高效地找到素数，定积分的计算，凸函数的极值问题，表达式求值，多项式乘法使用傅里叶变换，多项式求根采用牛顿迭代法，模线性方程组的解决，计算特定数字在数列中出现的次数，Rabin-Miller伪素数测试，快速幂取模，Lucas-组合数取模，快速组合数取模，菲波拉契数列的模运算，整数的质因数分解，递归求等比数列之和，置换群的最小交换代价，最优子区间，高精度计算，第K个与m互质的数，行列式的计算，排列P(n, m)的最后非零位，法雷级数，取石子游戏的策略，Nim游戏的必胜方法数，以及数列的最优划分问题。 这份笔记详尽地梳理了ACM竞赛中常见的算法和问题，对于提升算法思维和编程能力有着极大的帮助，是学习ACM竞赛和算法设计的宝贵参考资料。