Given the list of coordinates in the first quadrant, calculate how many right triangles can be formed that have one side parallel to the x axis

Question

Given the list of coordinates in first quadrant, calculate how many right triangles can be formed from them that have one side parallel x-axisand one side parallel y-axis.

I recently took part in a programming competition, in particular INOI (Indian National Olympiad n Informatics), and this was the first of two questions in the article.

In principle, I realized that any 3 points of type (a,y) (x,y) (x,b)form such a triangle, but they can’t do anything better, and in the end I just wrote the naive O (n ^ 3) (and all my friends).

Can anyone suggest a better way?

And please, THIS DOES NOT CONGRATULATE.

Answer 1

Allows numX[i] = how many points have i as their X coordinateand numY[i] = how many points have i as their Y coordinate.

We calculate how many triangles with the desired property exist for some point p. Without loss of generality, we can assume that pis the point at which the triangles have a right angle.

For this we need a point with the same coordinate Yand one with the same coordinate X. So what about this algorithm:

compute numX and numY in O(n).
num = 0
for each point p in the given list of points
    num += (numX[p.X] - 1)*(numY[p.Y] - 1)

output num

Basically, we can combine each point with the same coordinate Xwith each point with the same coordinate Yto get the desired triangle. Subtract 1to not consider pyourself.

O(n).

Answer 2

, . 2 * N, x y numX numY... wat IVlad ...