find the right triangles using coordinates

[StGuru]

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.

[yzaykov]

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.

[Muthuveerappan]

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

[yzaykov]

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).

[Muthuveerappan]

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.

[StGuru]

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.