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
algorithm
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