用于检测直角三角形的C程序

Question

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

Answer 1

这里是一个O（n^2日志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）的经典化（canonization） 。将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轴与单位矢量正交的矢量集是整个x-y平面，并且经典化的等价不能将该平面中的所有矢量映射到一个正交配对。