2019 ICPC南京K题Triangle解析：精确计算与线段二分

"这篇文档是关于2019年ICPC（国际大学生程序设计竞赛）南京站的一道题目——Triangle的解题思路和程序代码。文章主要涉及几何问题中的点与线段的关系判断，以及通过二分查找算法来确定特定三角形面积是否等于总面积的一半。" 在这篇文档中，作者探讨了一个编程竞赛中的几何问题，涉及到点在直线上的位置判断，以及如何利用二分查找算法解决相关问题。具体知识点如下： 1. **点在线段上的位置判断**：给定一个点和一条线段，可以通过叉积（cross）和点积（dot）来判断点相对于线段的位置。如果叉积结果的符号为0且点积小于等于0，则点位于线段上。这里使用了`dcmp`函数来处理浮点数比较的精度问题，避免因浮点误差导致的误判。 2. **叉积和点积**： - **叉积（Cross Product）**：对于两个二维向量，其叉积表示向量在垂直方向的投影长度乘积，可以用来判断两个向量是否垂直，以及点是否在向量形成的角平分线上。 - **点积（Dot Product）**：两个向量的点积表示它们在相同方向上的投影长度乘积，可以用于计算向量的长度和角度。 3. **二分查找算法**：在解决问题时，采用了二分查找策略来寻找特定的面积值。这个算法适用于已排序的序列，可以快速定位到目标值。在本题中，由于需要找到使得某个条件成立的边界，所以二分查找是有效的。 4. **二分查找的边界处理**：作者提到二分查找过程中需要注意边界条件的处理，特别是当左右边界缩小时，需要根据不同的端点进行处理。这是因为在某些情况下，二分查找可能因为边界处理不当而无法找到正确答案。 5. **浮点数精度问题**：在处理浮点数时，由于计算机表示浮点数的精度限制，常常会出现近似相等但不完全相等的情况。为此，文档中定义了一个`eps`常量，用于判断两个浮点数是否足够接近，从而避免因浮点误差导致的逻辑错误。 6. **自定义数据结构**：定义了`Point`和`Line`结构体，分别表示二维坐标点和线段，方便处理几何问题。 7. **编程规范**：文档中使用了C++的一些编程习惯，如`#define`宏定义、`using namespace std`、`iostream`输入输出流的同步关闭等，这些都是C++程序员常见的编程技巧。 8. **编程比赛背景**：ICPC（International Collegiate Programming Contest）是全球知名的大学生编程竞赛，题目通常具有挑战性和趣味性，要求参赛者在有限时间内解决复杂的问题并编写高效代码。 这个文档提供了一个解决几何问题的实际案例，通过二分查找法来解决面积比问题，对于理解和应用几何知识及算法有很好的参考价值。