find the right triangles using coordinates
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: find the right triangles using coordinates

  1. #1
    Join Date
    Mar 2009
    Posts
    82

    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.

  2. #2
    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. #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. #4
    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. #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. #6
    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.

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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center