我想找出一個n * m矩形網格內等腰直角三角形總數的重量值。權重值是在矩形網格中加上每個點值的總和。讓我通過一個例子找到等腰直角三角形的重量值
這裏解釋爲矩形網格，其中n = 1且m = 2。我想找出這個網格中每個等腰直角三角形的重量。以下是可從該網格來形成可能直角等腰三角形
所以我想找出每個這些三角形像三角形A具有4的權重值，B已6. 我嘗試使用C Program to detect right angled triangles找到直角三角形的總數，但如果我只知道有多少個三角形，則很難找到每個三角形的重量。我對這個問題的處理方法是挑選每個點並找出與之相關的三角形和相應的權重值。但是，網格中的點數需要4倍的時間複雜度（在這種情況下是4 * 2 * 3）。我想找到一個有效的公式，以便我可以對大n和m執行此操作。任何幫助，將不勝感激。
根據評論中的討論，您希望枚舉所有可能的三角形並發現邊上所有點的總和。
您可以按如下所示枚舉三角形。給定一個點p = (p1, p2)和另一個點q = (q1, q2)只有一個直角等腰從p開始，前往q並右轉。第三個頂點將在r = (q1 + q2 - p2, q2 - q1 + p1)。如果你遍歷所有的頂點對，這將會找到每個可能的三角形一次。
接下來我們需要每個線段的權重。給定從p到q的線段，首先找到(q1 - p1, q2 - p2)的GCD。 （特殊情況，任何整數的GCD和0都是1.）然後用這個GCD對這兩個係數進行劃分，以得到沿着該點從點到點的最小向量。我們稱之爲最小的矢量v。現在您可以將p, p+v, p+2v, ...的權重加起來，然後在q處停止。 （注意，每一行間隔應該包括一個點而不是另一個）。
然後你去了。最終的算法應該是。考慮到直角等腰三角形的數量是O(n^2 m^2)，這不能得到很大的改進。如果需要，可以通過遞歸(starting point, unit vector, n)的權重然後記憶它來改善對數因子。然而，這需要一個O(n^2 m^2)數據結構和地址問題解決它可能很容易超過理論性能增益。
好的，改進！而不是迭代點對，迭代開始向量v = (v1, v2)與(v1, v2)相對素數（檢查歐幾里得算法，然後在開始點p = (p1, p2)，然後在多個i的起始向量。您正在考慮的三角形將是(p1, p2), (p1 + n*v1, p2 + n*v2), (p1 + n*v1 + n*v2, p2 - n*v1 + n*v2)。現在，對於每個起始矢量，每個值爲p2 - p1，以及您可能要走的3個方向中的每一個，都可以計算出您可以從無窮大到該線上每個點的所有權重的總和（數據結構爲O(nm)）。）通過該數據結構，兩個內部循環可以在每個三角形中按時間執行O(1)。
這給你一個O(n^2 m^2)算法來找到所有O(n^2 * m^2)直角等腰三角形的總重量。這與你在理論上可以做到的一樣好。 （並且所需的輔助數據結構是O(nm)。）
在你的例子中 - 你爲什麼要改變節點的顏色？ –
C++標籤感覺不對。這是一個計算機科學問題;該解決方案在每種編程語言（或者至少在每個命令式編程語言中）中可能都是相同的。 –
@ChristianHackl對不起。我已經刪除了C++標記。 –