High School Maths
Given n triangles in cartesian plane, count the number of right triangles
Given a triangle, you have to tell if it is a right triangle. The author and tester used following property of right triangles.
C2 = A2 + B2
Where C is the length of longest side, A and B are length of other two sides.
int dist_square(point p, point q) return (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y) bool is_right_triangle(point p, point q, point r) c = dist_square(p, q) b = dist_square(p, r) a = dist_square(q, r) return 2*max(a, b, c) == a+b+c
The co-ordinates were kept very small so that there are no integer overflow errors.
Editorialist’s solution was based on the fact that dot product of two non zero vectors is zero iff they are orthogonal.
point operator-(point a, point b) return point(a.x-b.x, a.y-b.y) int dot(point p, point q) return p.x * q.x + p.y * q.y bool is_right_triangle(point p, point q, point r) point v1 = p-q point v2 = q-r point v3 = r-p return dot(v1, v2) == 0 or dot(v1, v3) == 0 or dot(v2, v3) == 0