计算几何：点、直线与相交问题

"该资源主要探讨了ACM竞赛中计算几何领域的基础知识，特别是关于点、直线和线段的关系。内容涵盖了点的坐标表示、精度处理、向量运算、内外积的几何意义、向量幅角计算、外积的应用以及线段相交的判断方法，并列举了一些相关的编程题目用于实践练习。" 在计算几何中，点是基本的元素，通常用坐标(x, y)来表示。点与点的关系可以扩展到判断它们是否位于同一直线的同侧或异侧，这涉及到线性代数中的向量和线性组合的概念。例如，当两点与直线的定向向量形成的角度相同（或相差180度）时，它们位于直线的同一侧。 描述中的"线段与直线相交"是一个常见的计算几何问题，解决这个问题需要理解直线的表示和线段的定义。直线通常由点斜式或一般式表示，而线段则是由两个端点定义的，判断它们是否相交要考虑端点的位置和直线的方向。 在处理精度问题时，由于浮点数计算可能存在误差，定义一个常量EPS来近似判断是否等于零。例如，如果一个数的绝对值小于EPS，则认为它近似等于零。此外，使用double类型进行计算可以提高精度，但要注意避免过多的除法、开方、三角函数等可能引入额外误差的操作。 向量运算包括加、减、点积和叉积。点积表示两个向量的长度乘积与它们夹角余弦的乘积，而叉积在二维空间中是一个实数，其正负表示两向量的旋转方向。叉积的绝对值还可以用来计算由两个向量张成的平行四边形的面积。 判断两点是否在直线上的问题可以通过向量外积来解决，外积的符号可以指示点相对于直线的方向。同样，外积也可以用于判断点是否在线段上，以及三点的顺序关系（顺时针或逆时针），进而解决点是否在三角形或凸多边形内部的问题。 线段相交的判断通常通过"排斥实验"和"跨立实验"这两种方法，分别检查线段的端点是否位于对方线段的两侧。直线的数据结构可以通过直线方程的一般形式表示，也可以归一化处理，使得某些系数恒为1，简化计算。 最后，资源提供了多个编程题目，如POJ1066、POJ1654等，这些题目可以帮助学习者巩固理论知识并提升实际编程解决几何问题的能力。通过这些题目，可以深入理解并掌握计算几何中点与直线关系的处理方法。