091. 具有整数坐标的直角三角形(Right triangles with integer coordinates)

在整数坐标处绘制点\(P(x_1,y_1)\)和点\(Q(x_2,y_2)\)并将它们与原点\(O(0,0)\)相连形成三角形\(\triangle OPQ\)

img

当每个坐标位于0和2之间时可以形成十四个包含直角的三角形,即\(0\le x_1,y_1,x_2,y_2\le2\),如下图:

img

给定\(0\le x_1,y_1,x_2,y_2\le50\),可以形成多少个直角三角形?

分析:这道题有一个显而易见的暴力解法,既遍历所有取值范围内的坐标,以原点组成一个三角形,再看这个三角形是否是直角三角形。因为这道题的数据规模不大,这种暴力方法应该也能得到结果,但是经过深入分析,我们可以发现一个更加高效的算法。我们可以根据直角三角形直角顶点所在位置把能够形成的直角形分成两类:一类是直角顶点位于坐标轴上的,这包括横轴、纵轴与原点;第二类是直角顶点不在坐标轴上的。

一、直角顶点位于坐标轴

这种情况又可以细分为三类:第一类是直角顶点位于原点,这时候另外两个顶点分别位于横轴与纵轴,分别有五十钟可能的取值,因此总共可以形成的三角形有\(50^2=2500\)种。第二类是直角顶点位于横轴上,假设其为\(P\),则\(P\)的坐标应为\((x,0)\),而\(Q\)位于与横轴垂直的直线上,则其坐标为\((x,y)\),同样的\(x\)\(y\)坐标各有五十种选择,则这种情况可以形成的三角形也是2500种。第三类是直角顶点位于纵轴上,和第二类情况完全一样,所以也有2500种选择,所以以上三种情况合计共有7500种选择。

二、直角顶点不在坐标轴上

这种情况则要相对复杂一些,需要用到一点入门的解析几何知识。不失一般性,我们假设点\(P(x_1,y_1)\)为直角顶点,则其与原点连线的直线的斜率\(k_1=y_1/x_1\),则与其垂直的直角边所在直线的斜率\(k_2=-x_1/y_1\),如下图所示:

img

显然,与直线\(OP\)垂直的直线上的整数点只要其取值在题目要求的取值范围内,则可以与\(P,O\)两点构成一个直角三角形,如图中的\(Q_1,Q_2,Q_3,Q_4\)点,现在的问题是如何求出这些点的坐标。

我们以点\(Q_1\)为例,从\(P\)点沿直线向右下移动就可以到达\(Q_1\)点,也即横轴坐标增加、纵轴坐标减小,假设横纵坐标单位变化值分别为\(\Delta x,\Delta y\),则两者分别为:

$$ \Delta x=\frac{y_1}{gcd(x_1,y_1)},\Delta y=-\frac{x_1}{gcd(x_1,y_1)} $$

这里的\(gcd(\cdot)\)表示最大公约数,之所以要除以最大公约数,是为了把斜率化简到最简形式,则设\(gcd(x_1,y_1)=g\),则可以通过以下方式得到所有直线\(PQ_1\)上的整数点:

$$ x=x_1+\frac{y_1}{g}\cdot t,\ y=y_1-\frac{x_1}{g}\cdot t $$

我们要求坐标必须在取值范围以内,假设取值范围为\([0,N]\),则有:

$$ 0\le x_1+\frac{y_1}{g}\cdot t\le N,\ 0\le y_1-\frac{x_1}{g}\cdot t \le N $$

则可以推出\(t\)的取值范围为:

$$ -\frac{g}{y_1}x_1\le t\le \frac{g}{y_1}\left( N-x_1 \right) ,\ \frac{g}{x_1}\left( y_1-N \right) \le t\le \frac{g}{x_1}y_1 $$

将两个取值范围合并,最终得到\(t\)的取值范围为:

$$ \max \left( -\frac{g}{y_1}x_1,\frac{g}{x_1}\left( y_1-N \right) \right) \le t\le \min \left( \frac{g}{y_1}\left( N-x_1 \right) ,\frac{g}{x_1}y_1 \right) $$

根据以上条件,我们只需要筛选出取值范围内的\(t\)的整数值个数,就是此种情况下可以形成的直角直角形个数。需要注意的是,在第一大类情况时,我们已经讨论了直角顶点位于横轴与纵轴的情况,所以此时作为直角顶点的\(x_1,y_1\)都不能零。

三、结论

最后我们把以上两种情况可以形成的直角三角形个数加起来,即为题目要求的直角三角形个数。代码如下:

# time cost = 3.28 ms ± 59.5 µs

from math import gcd

def main(N=50):
    count = 0
    for x in range(1,N+1):
        for y in range(1,N+1):
            g = gcd(x,y)
            low = max(-g*x/y,(y-N)*g/x)
            up = min(g*(N-x)/y,g*y/x)
            count += (int(up)-int(low))
    return count + 3*50**2