本资源主要涉及ACM竞赛中的计算几何问题,特别是关于交点的取舍规则和计算几何中的基础概念。重点讲述了如何处理交点、精度问题、向量运算以及内外积的几何意义,同时提供了判断两线段是否相交的方法,并列举了一些相关的编程题目。
1. 交点取舍规则:
- 扫描线与边相交且边位于两侧,计1个交点。
- 扫描线与边相交于端点,如果交点在下方,则计1个交点;在上方则不计。
- 边与扫描线完全重合的情况通常涉及到水平边的处理。
2. 基本数据结构:
- 使用`struct point_t`来表示点,包含`int x`和`int y`坐标,同时也可以作为向量的数据结构。
- 输入通常是整点,但在计算过程中要注意数据类型的使用。
3. 精度问题:
- 定义`const double EPS`用于判断接近0的值,通常使用如`is0(x)`这样的宏来检查。
- 选择合适的EPS值非常重要,因为它影响到浮点数比较的准确性。
- 建议多使用`double`类型,并避免除法、开方、三角函数和反三角函数等计算。
4. 向量运算:
- 包括加、减、点积和叉积。
- 点积可以表示两个向量之间的余弦相似度。
- 叉积在二维空间中是一个实数,可以用来判断两个向量的相对方向和它们构成的平行四边形面积。
5. 内外积的几何意义:
- 内积为负表示两向量夹角为钝角。
- 叉积(外积)为负表示夹角方向为顺时针,同时也代表了向量之间的面积。
6. 向量幅角计算:
- 避免直接计算角度,而应先确定向量所在象限,再通过外积进行比较。
- 如果需要具体角度值,使用`atan2(y,x)`,其值域为`(-π, π]`。
7. 外积应用:
- 判断三点拐向、求三角形面积、判断点的位置关系(在线上、线段上、多边形内等)。
- 对于大部分凸多边形问题,外积方法非常有效,但不适用于非凸多边形。
8. 判断两线段是否相交:
- 通过“排斥实验”和“跨立实验”来判断线段是否交叉。
9. 练习题目:
- 提供了多个POJ题目,涵盖了线段相交、多边形面积计算、点在多边形内的判断等计算几何问题。
10. 直线的数据结构:
- 使用`struct line_t`表示直线,通常包含三个系数`a, b, c`,表示方程`ax + by + c = 0`。
- 可以对直线进行归一化处理,确保`a`或`b`始终为1,便于计算。
11. 直线的数据结构(续):
- 考虑到输入通常为整点,可以使用两点定义直线,但需要注意处理特殊情况,如垂直线或水平线。
这个资源不仅介绍了计算几何的基本概念,还提供了实际编程竞赛中可能会遇到的问题及其解决方案,对于准备ACM竞赛或学习计算几何的人员来说非常有价值。