How to speed up the algorithm?

Question

Python

Good time of the day.
I have the following task: given two points A(x1, x2) and B(y1, y2), they are connected to the origin O(0,0) and form a triangle ABO between themselves. You need to find how many such right triangles will satisfy the condition: 0 <= x1, x2, y1, y2 <= N
This is what happened to me, but I'm ashamed of it (

def prod(A, B):
    return A[0]*B[0] + A[1]*B[1]

def check_triangle(x1, x2, y1, y2):
    OX = (x1, x2)
    OY = (y1, y2)
    XY = (y1 - x1, y2 - x2)
    sides = sorted([prod(OX, OX), prod(OY, OY), prod(XY,XY)], reverse = True)
    if sides[0]  ==  sides[1] + sides[2] and not 0 in sides:
        return sides

n = int(input()) + 1

def right_triangles(n):
    triangles = [[x1, x2, y1, y2] for x1 in range(n) for x2 in range(n) for y1 in range(n) for y2 in range(n) if check_triangle(x1, x2, y1, y2)]
    return len(triangles) // 2                  

print (right_triangles(n))

Any ideas how to make it faster? I will be very grateful for your help.
UPD. Integer coordinates

Answer 1

First, we take into account 3 * N ^ 2 triangles, in which the vertex with a right angle lies on one of the coordinate axes (or in general at the point (0,0)).
Now let's count all the other triangles.
Let (a,b) be the coordinates of a vertex with a right angle, 0 < a <= N, 0 < b <= N.
If c=gcd(a,b), a1=a/c, b1=b/c, then the remaining vertex must have coordinates (x,y)=(a+t*b1,bt*a1), where t is a non-zero integer.
The conditions 0 <= x,y <= N must be satisfied. Let's rewrite them as conditions on t:
-a/b1 <= t <= (Na)/b1, -(Nb)/a1 <= t <= b/a1 (note that a1, b1 are greater than zero, so you can divide). Given that t must be an integer, it lies on the segment from
t0 = -floor(min(a/b1,(Nb)/a1))
to
t1 = floor(min((Na)/b1,b/a1))
And, since the forbidden value 0 always belongs to this segment, we get that the number of triangles with vertex (a,b) is equal to t1-t0.
We go through all the points (a, b), calculate t1-t0 and summarize.
Everything. The complexity is N^2*log(N), most of the time is spent on calculating the GCD.
If you need it faster, you will have to think. Most likely, it will be necessary to sort through coprime pairs (a1,b1), count how many points fell into the skewed square (translated into the basis (a1,b1), (-b1,a1)), look for a formula for them and summarize. Maybe it will work, maybe not. What is the order of N?

Answer 2

As I understand it, you just sort through all possible options (I, alas, do not know python). Make up a system of equations and make its solution in a general form and substitute the initial data there. It will be faster.
Well, if anything, the coordinates of the points will look more correctly like this: A (x1, y1) and B (x2, y2).
Also, you have an error in your assignment. I understand correctly that x1, x2, y1, y2 must be integers (otherwise the problem has an infinitely large number of solutions).

Answer 3

Here are some thoughts on optimization:
1) check the right angle at a point using the scalar product.
(Ax*Bx+Ay*By)/|a|+|b| = 1
2) check not for the conformity of the rectangle, but only the angle at the first point.
3) check for a right angle only the vertices under the line x=y, and multiply the result by 2. Only you need to carefully handle the cases when the right angle lies on it.
4) As the second point, not all points should be sorted out, but only those that are inside the square described around the circle with the center at between (0,0) and our point, and outside inscribed in the same circle.
5) You can simply go along this circle: increase x, check whether y is integer. We don't even have to check the angle on a straight line.
I don’t know Python, so I don’t see where in the example it is divided by 2. Otherwise, each triangle becomes counted twice.

Answer 4

If you need to find the number of right-angled triangles with a right angle at the origin, then you can apply this trick: sort the points according to their angle to the OX axis, then run the loop, fixing the current point A[i], and the second B (i.e. the third vertex of the triangle) - we are looking for a binary search, knowing that its angle to OX is the angle A[i]+90 degrees. Complexity goes from your O(n^2) to O(nlogn).
If triangles are considered necessary if they can have a right angle 0AB or 0BA, then you can’t think of anything faster than brute force, IMHO