Find the number of congruent triangles?
- by avd
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.
