So in a recent algorithm contest I was given a task to create an algorithm that could construct a rectangle out of n triangles.

The information that is available to me is:

  • Width and height of the rectangle
  • Coordinates of all three corner points of each triangle
  • All triangles have to be used that are given
  • Triangles cannot be rotated
  • Triangles cannot overlap
  • It is always possible to construct a rectangle from the given triangles

I've spent some time googling for algorithms that could help me get started but I found nothing. So my question is, how do I go about solving such problem?

  • $\begingroup$ Can you add some more detail? Is it true that for the given triangle $soup$ it is always possible to construct such a rectangle? Can two triangles only meet on a boundary edge or may they overlap as long as the are inside the rectangle? Ist the rectangle axis aligned? $\endgroup$
    – gue
    Mar 15, 2018 at 18:07
  • $\begingroup$ I added the information for the first two questions, however the statement doesn't say anything about whether the rectangle should be aligned with axis or not. I'd assume it is always possible to make an axis-aligned rectangle or else they would've mentioned it in the statement. $\endgroup$ Mar 16, 2018 at 19:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.