C程序检测直角三角形
如果我在坐标系中给出100个点，我必须找到这些顶点中是否存在直角三角形。 有没有办法可以检测这些顶点中的直角三角形，而不必选择所有3个顶点对，然后在它们上应用毕达哥拉斯定理？ 可以有更好的算法吗？ 谢谢你的帮助。 🙂
这是仅针对两个维度的O（n ^ 2 log n）时间算法。 我将描述更高维度出了什么问题。
设S是具有整数坐标的点集。 对于S中的每个点o，构造一组非零向量V（o）= {p – o | p在S – {o}}中测试V（o）是否在线性时间内包含两个正交向量，如下所示。
方法1：将每个向量（x，y）册选为（x / gcd（x，y），y / gcd（x，y）），其中| gcd（x，y）| 是除x和y之间的最大整数，如果y为负，则gcd（x，y）为负，如果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 (ad - bc) < 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平面，并且相等的经典化不能将该平面中的所有矢量映射到一个正交配合。