C程序检测直角三角形

Question

如果我在坐标系中给出了100个点,我必须找到这些顶点中是否存在直角三角形.有没有办法可以检测这些顶点中的直角三角形,而不必选择所有3个顶点对,然后在它们上应用毕达哥拉斯定理？可以有更好的算法吗？谢谢你的帮助.:)

Answer 1

这是仅适用于二维的O(n^2 log n) 时间算法。我将描述更高维度中出现的问题。

令 S 为具有整数坐标的点的集合。对于 S 中的每个点 o，构造非零向量集 V(o) = {p - o | p in S - {o}} 并测试 V(o) 是否包含线性时间内的两个正交向量，如下所示。

方法一：将每个向量(x, y)标准化为(x/gcd(x, y), y/gcd(x, y))，其中|gcd(x, y)| 是除以 x 和 y 的最大整数，其中如果 y 为负，则 gcd(x, y) 为负；如果 y 为正，则 gcd(x, y) 为正；|x| 如果 y 为零。（这与用最低项表示分数非常相似。）关于二维的关键事实是，对于每个非零向量，恰好存在一个与该向量正交的规范向量，特别是 (-y, x) 的规范化。将 V(o) 中每个向量的规范化插入到集合数据结构中，然后对于 V(o) 中的每个向量，在该数据结构中查找其规范正交配对。我假设 gcd 和/或 set 操作需要时间 O(log n)。

方法2：在向量上定义比较器，如下所示。给定向量(a, b), (c, d)，写(a, b) < (c, d)当且仅当

s1 s2 (a d - b c) < 0,

在哪里

s1 = -1 if b < 0 or (b == 0 and a < 0)
      1 otherwise
s2 = -1 if d < 0 or (d == 0 and c < 0)
      1 otherwise.

使用此比较器对向量进行排序。（这与比较分数a/b与非常相似c/d。）对于 V(o) 中的每个向量 (x, y)，二分搜索其正交配对 (-y, x)。

在三维空间中，沿 z 轴与单位向量正交的一组向量是整个 xy 平面，而规范化的等效方法无法将该平面中的所有向量映射到一个正交配合。