0
$\begingroup$

My approach:- I separated the x coordinates and y coordinates in 2 separate arrays..then i used the idea of pythagoras theorem by selecting three vertices(1 from x axis and 2 from yaxis and vice versa) but it's taking too much time..can anybody suggest me a better approach?

$\endgroup$
1
$\begingroup$

Here is a simpler solution if points lay only on the axis running in time $O(n^2)$. scroll down for a solution for the general case for any set of points in the plane.

Let us distinguish three case of triangles. the first is when the origin is a point of the triangle (and hence it must be the right angle). The second case is where two points lay on the $x$ axis and the right angle is at the $y$ axis. The third is analogous where two vertices lay on the $y$ axis and the right angle is at a point on the $x$ axis. Let us solve the first two cases the third one can directly be derived from the second one.

The first case. Note that by excluding the origin from the set any point on the $x$ axis with a point on the $y$ axis form such a triangle with the origin so the number of such triangles is number of points on the $x$ axis times the number of points on the $y$ axis (excluding the origin).

The second case. Lets $X$ be the list of all points on the $x$-axis sorted in ascending $x$ coordinate and analogously we define the list $Y$ for points on the $y$-axis. $X$ and $Y$ can be build in time $O(n \log n)$. Note that for a fixed point on the $x$ axis the other point must be on the other side of the $y$-axis and as further it is from the axis, as further the $y$-vertex must be from the origin. So we can again use a sliding window approach. For each point $x_1$ to the left of the $y$-axix (we do the same later with the opposite side), iterate over all points $x_2$ to the right of the $y$-axis one by one from the left to the right and for each find the coordinate $y$ such that the points $x_1, x_2 (0, y)$ are a right-triangle wirth right angle at $y$. This can be found easily, since $y$ must be the point of intersection of the circle having $\overline{x_1 x_2}$ as a diameter with the $y$-axis. Note that $x_1, x_2 (0,-y)$ is also such a triangle. So we will keep two iterators starting at $y$ and one going upwards the other downwards, for each $x_2$ move both iterators till they reach a point whose absolute $y$-coordinate is not less than $y$. If it is equal to $y$ increase the number of triangles by one and iterate.


Here is an $O(n^2\log n)$ solution. For each point $p$ we will find the number of triangles that have a right angle at $p$ in time $O(n\log n)$. By iterating over all $p$ we can find the total count in the given time bound.

To this end let us sort all the points in polar angle relative to $p$ (we exclude $p$ from the set. Note that for a chosen candidate $p'$ we get that all triangles having an edge $\overline{pp'}$ have the third vertex at a fixed angle and hence all possible candidates appear consequently in the sorted list. So let us union all points having the same polar angle with $p$ in groups and keep a count for the size of each group. Now we can use a sliding-window approach to find for each group $g$ the group of points $g'$ (if it exists) such that $p$ forms a right triangle with each point of $g$ and point of $g'$. Note that by iterating over all groups we would have counted each triangle twice so we have to divide by 2 (or stop when the second pointer reach the first group).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ here the points either lie on the x axis or y axis,so keeping that in mind,could you provide a somewhat simpler solution? $\endgroup$ – ANKIT SINGHA Feb 15 at 16:43
  • $\begingroup$ Oh that was not very clear from the question I updated accordingly. It is much simpler now. $\endgroup$ – narek Bojikian Feb 15 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.