本资源主要涉及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竞赛或学习计算几何的人员来说非常有价值。
我的内容管理
展开
