我想找出一个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++标记。 –