-
March 13th, 2009, 06:39 AM
#1
find the right triangles using coordinates
I have one task that I can't solve recently.
The task:
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.
Thanks in advance.
Last edited by StGuru; March 13th, 2009 at 06:41 PM.
-
March 13th, 2009, 07:17 AM
#2
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.
-
March 13th, 2009, 07:58 AM
#3
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
-
March 13th, 2009, 08:45 AM
#4
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).
-
March 13th, 2009, 09:26 AM
#5
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.
-
March 13th, 2009, 12:00 PM
#6
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.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|