"这份资源是浙江大学的ACM竞赛模板，主要包含了ACMer在解决算法问题时经常用到的几何算法和相关知识，适用于准备ACM竞赛的选手学习和参考。"
在ACM竞赛中，几何问题是一类常见的题目，解决这类问题需要掌握一定的数学基础和算法技巧。以下是对几何部分知识点的详细解释：
1. 舍入规则：在处理浮点数计算时，需要注意舍入方式，特别是在涉及到比较和判断时，0.5的舍入方向可能导致结果错误。要确保处理好精度问题，避免因舍入误差导致错误。
2. 测试数据的全面性：对于几何问题，尤其是涉及对称性的题目，需要设计多种不对称的测试数据来验证算法的正确性。
3. 整数几何：在处理整数坐标下的几何问题时，要注意计算过程中可能会出现的边界情况，如乘法可能导致数值溢出（xmult和dmult）。
4. 符号点几何：在处理精度问题时，使用一个较小的常数eps（误差限）来判断两个浮点数是否接近，避免直接使用浮点数相等的判断。同时，避免除以可能为0的数值。
5. 角度计算：计算两个角度的差值时，应该在同一个2π范围内考虑，避免因角度跨越0和2π造成错误。相等判断也应考虑eps误差。
6. 斜率与除法：尽量避免使用斜率来表示直线，因为斜率可能会导致除0错误。在计算时，确保除数不为0，并在必要时使用atan2函数代替atan，atan2函数在(0,0)点有良好的定义。
7. 内积与外积：内积（点积）代表向量的夹角余弦，外积（叉积）代表向量的夹角正弦，它们分别用于判断两个向量的相对方向和计算面积。
8. 向量交叉点判断：通过计算向量叉积可以判断两个向量所表示的线段是否共线、顺时针或逆时针。叉积的绝对值代表这两条线段所围成的平行四边形面积。
9. 几何公式：
- 三角形半周长公式：P = (a + b + c) / 2
- 面积公式：S = a * h / 2 = abs(sin(C)) * a / 2 = sqrt(P * (P - a) * (P - b) * (P - c))
- 中线公式：Ma = sqrt(2 * (b^2 + c^2) - a^2) / 2
- 角平分线公式：Ta = sqrt(bc * ((b + c)^2 - a^2)) / (b + c)
- 高线公式：Ha = b * sin(C) = c * sin(B) = sqrt(b^2 - ((a^2 + b^2 - c^2) / (2 * a))^2)
- 内切圆半径公式：r = S / P
- 外接圆半径公式：R = abc / (4 * S) = a / (2 * sin(A))
10. 四边形性质：
- 对角线平方和与边长平方和的关系：a^2 + b^2 + c^2 + d^2 = D1^2 + D2^2 + 4 * M^2
- 四边形面积公式：S = D1 * D2 * sin(A) / 2
11. 圆的性质：
- 圆的面积公式：A = π * R^2
- 弧长公式：L =弧度 * R
- 勾股定理：在直角三角形中，半径R与弦AB的关系是R^2 = AB^2 / 2 + (R - h)^2，其中h是从圆心到弦AB的垂线长度。
这些是ACM竞赛中几何问题的基本知识点，掌握这些内容将有助于解决竞赛中的几何算法题。通过理解和熟练运用这些公式和技巧，ACMer可以在比赛中更有效地解决问题。
我的内容管理
展开
