用於檢測直角三角形的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平面，並且經典化的等價不能將該平面中的所有矢量映射到一個正交配對。