You are given some points on a 2-D plane. You are to determine the number of Isosceles-Right Angled Triangles formed by these points. Here is a direct link to the problem.
At first the problem was looking a bit difficult. A brute-force approach would be to check all triplets of points and see if they form such a triangle, resulting in $O(N^3)$.
The number of points were about $10^5$ which implies you need a way better solution and this is my approach:
Divide all the points into groups based on X-coordinate and Y-coordinate. This means that each point belongs to two groups, one pertaining to its X- and the other to its Y-coordinate.
For each point, consider its X-coordinate group and Y-coordinate group. We will count all those triangles that form a $90^{\circ}$ angle at the current point. Clearly, the other two points must come from the X- and Y- coordinate groups.
Now the question trims down to how efficiently we count such triangles. Although it may look like $O(N^2)$ for a moment, it can actually be done in $O(N)$! We have two perpendicular lines(X- and Y-coordinate group) meeting at the current point. Consider an imaginary hypotenuse moving away from the current point making an angle of $45^{\circ}$ with the lines. For every point of intersection which is an integer on the perpendicular lines, we check if both the points exist one in each group and then count it as a valid triangle.
Now, instead of moving the hypotenuse by a single unit, we directly move it to the nearest next valid point on the lines, whichever is minimum and check if the other point exists. Now, this drastically reduces the time-complexity. To give a more clear understanding, see the example below:
As you can see, we initially we move the hypotenuse directly to point 1. This gives a valid triangle, since point 2 also exists. Now we move the hypotenuse to next nearest point from 1 or 2 whichever is minimum, which gives 3 in this case. But since 3 doesn't have a valid point on the other line, we then move to the next nearest point which is 6, but this too doesn't have its corresponding point either. Next we move to 4 (or 5) and they make up a valid triangle.
In this way, no matter what the co-ordinates are, this whole operation is taking not more than $O(N)$. And remember since there are 4 different planes, the hypotenuse has to be moved in four-directions. This procedure has to be applied for every given point.
Time-complexity:
Now, coming to time-complexity, although at a first glance, it may look like $O(N^2)$, its actually less than that. It takes $O(NlogN)$ to sort out the points into groups and an amortized time of $O(k.N)$ for the counting process, where $k$ is the maximum number of points on a single line, either horizontal or on vertical line. Although, this may not be a tight bound, but still it suffices. The worst case happens when all the points form a complete square.
For a square of side $n$, there are as many as $$2.n.(n+1).(2n+1)\over3$$ number of right-angled isosceles triangles which is $O(N^3)$, but since $N=\sqrt {10^5}$(remember its a square), we can have at most $3.10^7$ triangles, which explains there is such a test-case since my code took $\approx 1.5$ seconds to execute. I hope you have understood my idea :)
