algorithm - C Program to detect right angled triangles -

algorithm - C Program to detect right angled triangles -

if given 100 points in coordinate system, , have find if there exist right angled triangle in vertices. there way can observe right angled triangle among vertices without having take pairs of 3 vertices , applying pythagoras theorem on them?? can there improve algorithm this? help. :)

here's o(n^2 log n)-time algorithm two dimensions only. i'll describe goes wrong in higher dimensions.

let s set of points, have integer coordinates. each point o in s, build set of nonzero vectors v(o) = {p - o | p in s - {o}} , test whether v(o) contains 2 orthogonal vectors in linear time follows.

method 1: canonize each vector (x, y) (x/gcd(x, y), y/gcd(x, y)), |gcd(x, y)| largest integer divides both x , y, , gcd(x, y) negative if y negative, positive if y positive, , |x| if y zero. (this similar putting fraction in lowest terms.) key fact 2 dimensions that, each nonzero vector, there exists 1 canonical vector orthogonal vector, specifically, canonization of (-y, x). insert canonization of each vector in v(o) set info construction , then, each vector in v(o), canonical orthogonal mate in info structure. i'm assuming gcd and/or set operations take time o(log n).

method 2: define comparator on vectors follows. given vectors (a, b), (c, d), write (a, b) < (c, d) if , if

s1 s2 (a d - b c) < 0,

where

s1 = -1 if b < 0 or (b == 0 , < 0) 1 otherwise s2 = -1 if d < 0 or (d == 0 , c < 0) 1 otherwise.

sort vectors using comparator. (this similar comparing fraction a/b c/d.) each vector (x, y) in v(o), binary search orthogonal mate (-y, x).

in 3 dimensions, set of vectors orthogonal unit vector along z-axis entire x-y-plane, , equivalent of canonization fails map vectors in plane 1 orthogonal mate.

c algorithm