《挑战程序设计竞赛》笔记
点的映像：几何变换的精妙之处
在程序设计竞赛中，几何问题常是考察算法设计和数学推导能力的重要环节。《挑战程序设计竞赛》一书中，作者渡部有隆以其独特的视角，为我们揭示了点对称变换的精妙之处。书中通过图16.7生动地展示了点p关于线段s=p1p2的映像x的求解过程。这种变换可以通过以下三个步骤实现：首先，求点p到线段s的投影点p’；然后，将向量p’-p的长度扩大一倍；最后，以p为起点，沿着这个方向移动，得到点x的坐标。
这种映像变换在实际应用中有着广泛的场景。例如，在计算机图形学中，点对称变换可以用于生成对称图形；在游戏开发中，可以用于计算物体的反射路径。通过这种变换，我们可以更好地理解几何世界中点与线段之间的关系。
书中还提供了具体的程序实现，例如Program16.16，通过向量运算和投影计算，轻松实现了点对称变换。这种将几何问题转化为代数计算的方法，体现了程序设计竞赛中数学与算法的深度融合。
距离计算：从点到线段，再到线段之间
距离计算是程序设计竞赛中的基础问题之一。在第16.5节中，作者详细讲解了两点间距离、点与直线距离、点与线段距离以及线段与线段之间的距离计算方法。这些内容不仅是几何学的基础，也是解决复杂问题的关键。
例如，两点间的距离可以通过向量的模长计算，点与直线的距离可以通过向量的外积计算，点与线段的距离则需要考虑多种情况：点是否在射影点的投影范围内，或者是否需要直接计算到端点的距离。这些情况的判断需要通过向量的内积和外积来实现。
书中还提供了具体的程序实现，例如Program16.19，通过判断向量的内积是否为负，来确定点p是否位于线段的延长线上。这种方法不仅高效准确，也体现了算法设计中的优雅。
线段与线段的距离：复杂问题的简洁解决方案
在第16.5.4节中，作者讨论了线段与线段之间的距离计算问题。这种问题在实际应用中具有重要意义，例如在路径规划和碰撞检测中。解决方案包括计算线段端点之间的距离，以及判断线段是否相交。
书中提到，线段与线段之间的距离是四个可能距离中的最小值：线段s1的两个端点到线段s2的距离，线段s2的两个端点到线段s1的距离。此外，如果两条线段相交，则距离为0。这种方法通过分解问题，将复杂的几何计算转化为多个简单的距离计算问题。
逆时针方向判断：向量外积的应用
在第16.6节中，作者介绍了如何判断三个点是否按逆时针方向排列。这一问题在计算几何中具有重要意义，例如在多边形的凸性判断和平面分割问题中。通过向量外积的符号，可以快速判断点的位置关系。
书中提供的Program16.21通过计算向量的外积，判断点p2是否位于向量po→pl的逆时针方向。这种方法不仅高效，而且代码简洁，体现了算法设计中的优雅。
通过这本书的学习，我们可以更好地理解程序设计竞赛中几何问题的解决方法，从而在实际比赛中更得心应手。