0091 整点勾股数
* * * *
拉格朗日计划
* * * *
整点三角形

考虑坐标为整数的点$P(x_1,y_1)$和$Q(x_2,y_2)$,它们和原点$O(0,0)$构成三角形$\triangle OPQ$。



当$x_1,y_1,x_2,y_2$在$[0,2]$之间时,有14个这样的三角形:



当$x_1,y_1,x_2,y_2$在$[0,50]$之间时,有多少个这样的三角形?

本题难度:



解答

用$L$表示横、纵坐标都在$[0,50]$之间的整点,遍历从$L\setminus\{(0,0)\}$中选出两个不同点A、B的全部可能(大约$\binom{51^2-1}{2}\approx$三百万种情况)。

用内积是否为0检验$AO\perp BO$, $AO\perp AB$, $AB\perp BO$中是否有一项成立(即能构成直角三角形态), 结果是$14234$。

import itertools
p=[[i,j] for i in range(51) for j in range(51)][1:]
print sum(1 for x,y in itertools.combinations(p,2) if x[0]*y[0]+x[1]*y[1]==0 or x[0]*(x[0]-y[0])+x[1]*(x[1]-y[1])==0 or (x[0]-y[0])*y[0]+(x[1]-y[1])*y[1]==0)