Judge's Notes on Triangle Cuts

triangle topologies and labelling
The figures above are referenced in the source code triangle.java, using the triangle labels A-D and labeling the angles with array indices 0-2. Pic 3 and 4 are also referenced below in the discussion of cases where there is no cut from one vertex of the original triangle straight to a point on the opposite side.  There the additional labels for points P, Q, R, X, Y, and Z are used.  The argument below shows that the solution considers all the necessary cases where the original triangle is not directly cut into two triangles.

Pattern Cases of a triangle T = PQR is cut in pieces three times, generating atomic triangles, A, B, C, D:

Each pair of subcases below partition all the possible cases they are concerned with.
  1. Triangle T is cut along a straight line running from one vertex of T to the opposite side.
  2. There is no cut from a vertex of T to the opposite side.  The first cut must go from some interior point of one side of T to another.  This cuts off the one of the vertices of T, (call it P), and leaves a quadrilateral, (call it XYQR as in Pic 3 and 4).  The remaining two cuts must come from the quadrilateral, since the only way to cut the quadrilateral into two triangles with a single cut would be to cut between opposite vertices, either QX or RY, and either of these would be a cut from a vertex of T all the way across T.  Furthermore the next cut must have an endpoint somewhere along QR:   If not, the remaining part that does contain QR and at least parts of QY and RX is either a quadrilateral that again can only be split into triangles with a cut all the way across T from Q or R, or it includes a vertex in the interior of XY, and is a pentagon which cannot be cut into two triangles at all.
    1. The second cut has an endpoint at Z on the interior of QR.  The other endpoint cannot be in the interior of XY because two quadrilaterals are produced that cannot both be cut in triangles with one more cut.  It cannot go to the interior of QY or RX because it forms a pentagon that cannot be split into two triangles.  Hence it must end at X or Y (suppose X).  The quadrilateral ZXYQ again may not be cut across T on QX, so it must be cut on ZY, generating the pattern of Pic 3 above.
    2. The second cut has an endpoint at Q or R ( call it Q).  It cannot go all the way across T to a point on RX, so it must intersect a point Z in the interior of XY.  The remaining quadrilateral QZXR can only be cut in triangles without crossing all of T from vertex Q by using RZ, generating the pattern of Pic 4.    

Cutting a Triangle Twice

Whenever a triangle is cut only twice, ending up with three triangles, one of the cuts must go all the way across from a vertex:  Even if the first cut does not go all the way across and generates the quadrilateral XYQR as above, the single remaining cut must go all the way across T on QX or RY.

Ignoring side length. 

With a single cut being made each time, the lengths of the sides can always be made to work out correctly.  The common length of the part cut (or joined in my approach to the algorithm) always allows one single factor to be determined to allow one part to be scaled to fit. 

The original (junked) version of this problem allowed situations like Figure 4, where sometimes a part can only be added by matching two different edges, and the measurement of edges becomes necessary to completely consider these cases.  The current statement of the problem avoids this considerable complication.

Judge's Data

Most solutions are formed from successively joining two triangles.  Input triangles are called A-D, and notation like (AB) means A and B with A on the left and B on the right as viewed in Pic 1 or Pic 2. The angles are also shown if it is a partial result:
Dataset
1-4.  Examples
5.  First example with last triangle flipped (also in sample input)
6.  Pic 3 with A in center
7.  Pic 4 with C at the top and D at the bottom.
8.  (BC 70 30 80)(AD 100 30 50)
9.  (BA 45 85 50)(CD 60 95 25)
10.  (AC 20 100 60)(DB 15 85 80)
11.  (BD 20 105 55)(AC 75 40 65)
12.  (CA 45 30 105)(DB 35 70 75)
13.  (AD 95 50 35)(CB 35 60 85)
14.  (A(DB 75 45 60) 40 80 60)C
15.  D(C(AB 50 50 80) 50 80 50)
16.  A((BC 80 80 20)D 20 100 60 )
17.  D((BC 10 20 150)A 10 30 140)
18.  fails with the daughter's rules
19.  lots of angles go together, but fails without a flip
20.  Pic 3 among other possibilites
21-25.  Sets 6-10 with the big triangle flipped; all fail
26-30.  Sets 11-15 with the last triangle flipped; all fail