计算机几何基础：线段与多边形计算方法

本周的主题是"计算机几何基础"，由杭州电子科技大学刘春英教授讲解，主要涉及ACM程序设计中的计算几何知识。课程分为两个单元，第一单元探讨了线段的属性，包括如何理解和应用线段的长度、方向等基本特性。学生们被引导思考传统的计算线段相交的方法，以及这种方法与基于向量的计算几何方法之间的区别，强调了这三个属性在求凸包等复杂几何问题中的基础作用。 第二单元重点讲解了多边形的面积计算，特别是对于简单多边形的面积求解。首先，通过解析几何中的海伦公式介绍了解析方法，指出其缺点在于计算量大且可能存在精度损失。接着，引入计算几何的方法，利用向量的叉积来计算三角形面积，这种方法不仅简化了计算，还能保持更高的精度。特别提示了有向面积的概念，区分了不同情况下三角形面积的正负。 在课程中，教授特别提到了如何利用凸多边形的三角形剖分来计算其总面积，通过连接凸多边形的顶点构造内部三角形，并利用有向面积的累积来得出结果。这一部分的教学旨在帮助学生掌握计算几何的基本技巧，为解决实际的ACM编程问题打下坚实的基础。 整个课程以互动方式展开，鼓励学生主动思考和探索，通过具体的例子和练习，使理论知识与实践操作相结合，提升学生的计算机几何问题解决能力。这对于参加ACM竞赛的学生来说，是一次重要的技能提升和知识深化的机会。