# Solutions for Problem 91

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is, 0 ≤ x1, y1, x2, y2 ≤ 2.

Given that 0 ≤ x1, y1, x2, y2 ≤ 50, how many right triangles can be formed?

## Python by Althalus

Runtime: 18ms

Oh gods. I have drawn so many grids and triangles in the past day trying to find these patterns that I never want to see another triangle again.

Methinks you are slowly turning into Maximillian Cohen from Pi... - tom (16/4/2010).

```from time import time
start = time()

from fractions import gcd # How nice. Python 2.6 provides a GCD implementation for me!

max=50

# right angle in bottom left or bottom right, and the first inverted.
# (0,0), (0,y), (x,0)  (0,0),(x,0),(x,y)  (0,0),(0,y),(x,y)
count = max*max*3

# triangles where long side flush with vertical/horizontal, and triangles that can be formed therein.
c2=0
for i in range(1,max):
for j in range(1,i+1):
if i+j > max: break
c2 += 2
count += c2

c2 = 0
# triangles not flush with a vertical/horizontal
for i in range(1,max+1,1):
for j in range(i+1,max+1): # We can take advantage of the fact that x.y is equivelant to y.x to halve the number of loops
if i == j: continue # covered above.
c3 = 0
d = gcd(i,j)
i1 = i/d
j1 = j/d
x,y = i+j1, j-i1
while x <= max and y >= 0:
c3 += 2
x += j1
y -= i1
x,y = i-j1, j+i1
while x >= 0 and y <= max:
c3 += 2 # See comment above.
x -= j1
y += i1
c2 += c3
count += c2
print count
print time()-start
```