TJU ACM模板：算法与计算几何总结

"天津大学 ACM 模板是一个专门为参与 ACM 竞赛的学生设计的学习资料，主要面向本科阶段，从大二到大四的学生。这个模板涵盖了算法、数据结构和计算几何等多个领域的知识，旨在帮助参赛者提升解决问题的能力。模板由 tmeteorj 编写并不断更新，包括了多个版本的修订，如 V1.0 和 V2.0。内容详实，适合用于学习和备赛。" 以下是模板中的主要知识点： 1. 图论： - 割点割边：在图中具有特殊地位的节点和边，移除它们会导致图的连通性发生变化。 - 树的分治：利用树的结构进行问题分解，通常用于解决递归性质的问题。 - 最大匹配：寻找无向图中最大的配对数，常通过匈牙利算法或 Dinic 算法解决。 - 最大环：找出图中最大的环。 - 最大流：网络流问题的一部分，寻找从源点到汇点的最大流量，Dinic 算法和 Sap 算法是常用的求解方法。 - 平面图网络流：处理可以在平面上展开而不相交的图的网络流问题。 - 混合图的欧拉回路：混合图包含有向和无向边，寻找能够遍历所有边且仅经过每个节点一次的路径。 - 最大权闭合图：寻找具有最大权重的闭合子图。 - 最大密度子图：寻找图中密度最大的子图。 - 最小边割集：找到使图变得不连通所需的最小边集合。 - 二分图最小权覆盖集：在二分图中找到覆盖所有节点的最小权重边集合。 - 最优比例生成树：寻找边权与树中任意两节点间距离成比例的生成树。 - 曼哈顿距离生成树：构建使得树中任意两个节点间曼哈顿距离之和最小的树。 - 最小度生成树：寻找树中边权最小的生成树。 - 次小生成树：除了最小生成树外的次优选择。 2. 计算几何： - 公式和算法：包括直线的一般式和两点式转换、点的旋转、向量的倾斜角计算、点与线段的关系等。 - 点到线、线段的距离计算：求点到直线或线段的最短距离，并找到最近的点。 - 矢量夹角：计算矢量之间的夹角及其余弦值。 - 直线的斜率和倾斜角：计算直线的斜率并将其转换为角度。 - 点关于直线的对称点：找到一个点关于给定直线的对称点。 - 多边形的判断和操作：判断多边形是否为凸多边形、是否逆时针排列，以及点是否在多边形内部或线上等。 这个模板不仅包含了理论知识，还提供了实际的计算几何库函数，有助于理解和实现这些算法，是学习和实践 ACM 竞赛问题的重要参考资料。