ACM计算几何要点：精度处理与向量运算

"ACM+计算几何+必看.ppt" 在ACM（国际大学生程序设计竞赛）中，计算几何是一个重要的领域，对于参赛者来说，理解和掌握相关知识至关重要。这份资料主要涵盖了计算几何的一些基础概念和技巧，由刁瑞在2007年ACM协会暑期集训中分享。 首先，计算几何中经常涉及到浮点数的运算，通常推荐使用`double`类型而非`float`，因为`float`可能会因精度问题导致错误结果。在判断一个`double`值是否接近于0时，不能直接用`x == 0`，而是应该使用如`x < eps && x > -eps`这样的方式，其中`eps`是预设的精度阈值，例如`0.000001`。此外，避免在表达式中出现可能导致精度损失的运算，如除法、开方和三角函数。 圆周率π在计算几何中也非常重要，可以使用3.141592654这样的近似值，或者利用`acos(-1)`来获取更精确的π值。角度和弧度之间的转换也是需要了解的，C/C++的标准库函数如`sin`, `cos`, `tan`等都期望输入是弧度而不是角度。 在处理向量时，通常会定义一个结构体或类来表示二维向量，如`struct point`，包含`x`和`y`坐标。为了方便操作，可以重载加法、减法和向量乘法操作。向量有两种乘法：内积（点积）和外积（叉积）。点积`α·β`是向量α在向量β上的投影长度乘以β的长度，而叉积`α×β`可以用来计算两个向量所张成的平行四边形的有向面积。在实际编程中，可以根据题目需求重载相应的运算符。 外积的符号判断常用于解决几何问题，例如通过右手定则可以确定两个向量旋转形成的角是顺时针还是逆时针。此外，外积还可以用于判断两个向量是否平行或垂直，以及求解向量的正交分解等问题。 这份资料提供了一个计算几何的基础教程，包括了数据类型的选择、精度控制、向量运算以及其在ACM竞赛中的应用。学习这些内容有助于提高解决几何问题的效率和准确性。