我想找出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。（特殊情况。任何整数和0的GCD都是1。）然后将两个系数除以GCD，得到沿该线从一个点到另一个点的最小向量我们把这个最小的向量称为v现在您可以为p, p+v, p+2v, ...添加权重，然后在q停止。（注意，每行间隔应包括一个点，而不是另一个点。）
就这样。最后的算法应该是O(n^2 m^2 log(n+m))直角等腰三角形的个数小于cc>时，这一点没有太大的改进如果需要，您可以通过使O(n^2 m^2)的权重递归来改进日志系数，然后记住它然而，这需要一个(starting point, unit vector, n)的数据结构和解决它的局部性问题很容易超过理论性能增益。
好的，进步！不是在点对上迭代，而是用相对素数在起始向量上迭代（用欧几里德算法检查，然后在起始点上迭代，然后在起始向量的倍数上迭代）您正在考虑的三角形将O(n^2 m^2)。现在对于每一个起始向量，每一个v = (v1, v2)的值，以及你可以走的三个方向中的每一个，你可以计算从无穷远处到那条线上每一点的所有权重之和（a(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）。