How many right triangles can be built from points

Question

There are array of points, I need to determine how many right-angled triangles can be built from them.

This is a task for both programming and geometry.

Because the number of points can be very large, and the time to run the program is limited.

Please tell me whether it is possible to somehow derive a formula to determine the number of possible triangles.

Input format: The first line contains a single integer N - the number of points in the set Next, N lines contain two integers: xi, yi

My code:

from math import sqrt

def f(x1,y1,x2,y2,x3,y3):
    a = [(x2-x1)**2+(y2-y1)**2, (x3-x2)**2+(y3-y2)**2, (x1-x3)**2+(y1-y3)**2]
    a.sort()
    if a[0]+a[1]==a[2]:
        return True
    return False 

N = int(input())
ar = []
for i in range(N):
    ar.append([int(j) for j in input().split()])

count = 0
for ia in range(N):
    for ib in range(N):
        for ic in range(N):
            if ia!=ib and ia!=ic and ib!=ic :
                a = ar[ia]; b = ar[ib]; c = ar[ic]
                if f(a[0],a[1],b[0],b[1],c[0],c[1]): 
                    count+=1
print(count//6)

my code goes beyond time limits

P.S. DSolved the problem using vectors, also does not pass in time

def f1(x1,y1,x2,y2,x3,y3):
    a = [x2-x1,y2-y1]
    b = [x3-x2,y3-y2]
    if a[0]*b[0]+a[1]*b[1] is 0:
        return True 
    return False

N = int(input())
ar = []
for i in range(N):
    ar.append([int(j) for j in input().split()])

count = 0
for ia in range(N):
    for ib in range(N):
        for ic in range(N):
            if ia!=ib and ia!=ic and ib!=ic :
                a = ar[ia]; b = ar[ib]; c = ar[ic]
                if f1(a[0],a[1],b[0],b[1],c[0],c[1]): 
                    count+=1 
print(count//2)

Beginning of implementation of the algorithm with polar angles:

from math import *

def polar(a,b):
    res = atan2(b,a)
    if (res < 0) :
      res += 2 * pi
    return res

N = int(input())
A = []

for i in range(N):
    A.append([int(j) for j in input().split()])

DS = []
for i in range(N):
    p = A[i]
    for j in range(N):
        if j!=i:
            D = [A[j][0]-p[0], A[j][1]-p[1]]
            ang = polar(D[0],D[1]) 
            DS.append(ang)

DS.sort()
#what's next?

Answer 1

There is an $\mathcal{O}(N^2\log N)$-time algorithm, coming from an ability to compute, for each point $P$, the number of right angles at $P$, in $\mathcal{O}(N\log N)$ time. This can be done by considering the (other) points in the polar coordinate system with the origin at $P$, and sorting by polar angle, after which the counting is easy. (Actually there's no need to compute the polar angles - this is just an idea to be used indirectly.)

Answer 2

The answer is dependent on the position of the points. So I think Brute force method is the only way, i.e you will have to consider various combinations of triplets of points. So no, I don't think you will be able to use any simple formula to solve the problem. But using nested loops this can be solved fairly easily.