CODEWITHSUNDEEP
algorithm
shreyansh
shreyansh

Reputation: 107

Number of right angled triangles given n points

Given n points in the xy plane, I need to find the number of right angled triangles that can be formed using these points as vertices. I did come up with a O(n3) solution where you take 3 vertices at a time and check if they form a right angled triangle. I wanted to know a more optimal solution for this problem.

Upvotes: 3

Views: 1763

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

An O(n^2) solution could be something like this:

  • Iterating through each point one by one,
  • When processing each point, calculate the unit vector that formed by that point and other point in the list; then store them in a HashMap. For each of those vector, calculate the unit vector that formed a right angle with it and look it up in the HashMap.

Upvotes: 6

Related Questions