Find the number of congruent triangles?

Posted by avd on Stack Overflow See other posts from Stack Overflow or by avd
Published on 2009-10-05T05:23:56Z Indexed on 2010/06/13 22:52 UTC
Read the original article Hit count: 239

Filed under:
Say I have a square from (0,0) to (z,z). 
Given a triangle within this square which has integer coordinates 
for all its vertices.
Find out the number of  triangles within this square which are 
congruent to this triangle and have integer coordinates. 
My algorithm is as follows--


 1) Find out the minimum bounding rectangle(MBR) for the given triangle.
 2) Find out the number of congruent triangles, y within that MBR,
    obtained after reflection, rotation of the given triangle. 
    y can be either 2,4 or 8.
 3) Now find out how many such MBR's can be drawn within the given 
    big square, say x;
    (This is similar to finding number of squares on a chess board)
 4) x*y is the required answer.

Am I counting some triangles more than once or I am missing something by this algorithm? It is a problem on online judge? It gives me wrong answer. I have thought a lot about it, but I am not able to figure it out.

© Stack Overflow or respective owner

Related posts about algorithm