C程序检测直角三角形

Question

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

Answer 1

这是一个O(n^2 log n)-time 算法，用于仅二维。我将描述更高维度的问题。

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

方法一:将每个 vector (x, y)规范化为(x/gcd(x, y), y/gcd(x, y))，其中|gcd(x, y)|是同时除以 x 和 y 的最大整数，如果 y 为负，则 gcd(x, y) 为负，如果 y 为正，则为正，并且 |x|如果 y 为零。 (这与用最低项表示分数非常相似。)关于二维的关键事实是，对于每个非零 vector ，恰好存在一个与该 vector 正交的规范 vector ，具体来说，(-y, x) 的规范化.将 V(o) 中每个 vector 的规范化插入到一组数据结构中，然后，对于 V(o) 中的每个 vector ，在该数据结构中查找其规范正交配对。我假设 gcd 和/或设置操作需要时间 O(log n)。

方法 2:在 vector 上定义一个比较器，如下所示。给定 vector (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.

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

在三个维度上，与沿 z 轴的单位 vector 正交的 vector 集是整个 x-y 平面，等价于经典化无法将此平面中的所有 vector 映射到一个正交伙伴。