How many right triangles can be built from points

geometrypythontriangles

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?

Best Answer

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.)

Related Question