CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: find the right triangles using coordinates

1. Member
Join Date
Mar 2009
Posts
82

## find the right triangles using coordinates

I have one task that I can't solve recently.

The number of coordinates and the coordinates them self are given in file.

Now we need to find how many right triangles can be created using these coordinates and paste the output.
Last edited by StGuru; March 13th, 2009 at 06:41 PM.

2. Member
Join Date
Mar 2009
Location
Bulgaria
Posts
63

## Re: find the right triangles using coordinates

The brute force you are talking about has asymptotic complexity O( n^3 ). You can go down to O( n^2 * lg(n) ) if you do the following...
1. For each point A precompute the angel of the line AB for each point B - O( n^2 )
2. Sort the lines of the just generated matrix - O( n^2 * lg(n) )
3. For each line AB binary search through the list of precomputed angles of point A for the desired angle - O( n^2 * lg(n) )
Be careful for roundings.
Sorry, that's the best I can come up with.

3. Join Date
Feb 2009
Posts
326

## Re: find the right triangles using coordinates

Consider the 3 co-ordinates in a right angle triangle to be P, Q and R.

Assume the following:

distance between PQ = a
distance between QR = b
distance between PR = c

In a right angle triangle c^2 = SQUARE ROOT OF ( a^2 + b^2)

Distance between 2 co-ordinates say (x1, y1) and (x2, y2) can be calculated by the formula:

distance = SQUARE ROOT OF ( (x2-x1)^2 + (y2-y1)^2))

1) So calculate the distance between all the various possible combination of co-ordinates.
2) Then see for which of them the formula fits in.

See this link as a reference - http://www.teacherschoice.com.au/Mat...try/Alg_15.htm

Hope it helps, good luck

Regards,
Muthu

4. Member
Join Date
Mar 2009
Location
Bulgaria
Posts
63

## Re: find the right triangles using coordinates

That's still O( n^2 * lg(n) ) if implemented correctly, but definitely easier to be written than mine.
There are also no rounding problems, because you never need to calculate the square root (having the squared distance between two points is actually what you really need).

5. Join Date
Feb 2009
Posts
326

## Re: find the right triangles using coordinates

corrected formula is pasted below:

c = SQUARE ROOT OF ( a^2 + b^2)

I agree with yzaykov, you can square on both sides, so as to avoid computing square root.

6. Member
Join Date
Mar 2009
Posts
82

## Re: find the right triangles using coordinates

Thanks all for the replies. Muthuveerappan, yes that's the method I will use if there isn't other.
yzakov, I can't clearly understand what u mean by O(n^2*lg(n)). Could you please PM me with the message on Bulgarian? Thanks again for the help.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•