Cut It Out!
Time Limit: 5000 ms Memory Limit: 65536 KiB
Television’s Toddler Time’s topic taught to toddler Tommy Tiwilliger today was triangles (and the letter T)! Tommy became so enamored by triangles that immediately after the show ended, he grabbed his safety scissors and the nearest sheets of paper he could find and started cutting out his own triangles.
After about 15 minutes each paper had one triangular shaped hole cut out of it. But Tommy wasn’t finished yet. He noticed he could divide each of the original triangles into two triangles with a single cut starting from one corner. He spent another 15 minutes doing just that. Things would have gone along swimmingly, except that Tommy’s mother eventually came into the room and noticed that the original sheets of paper were part of a very important document for a legal case she was working on (involving a lover’s triangle). After carefully removing Tommy from the room and counting slowly to 10 (a triangular number), she went about trying to reconstruct the pages after gathering together the now randomly scattered triangles. Your job is to help her by writing a little program to determine which triangles go where (and try to get it done before tomorrow’s episode of Toddler Time on papier-mâchè).
Each test case will start with an integer n ≤ 20 indicating the number of holes cut out, followed by the coordinates of the holes, one hole per line. These holes are assumed to be numbered 1, 2, . . . , n.
Following this will be the coordinates of the 2n triangles resulting from the bisections, one triangle per line. These triangles are assumed to be numbered 1, 2, . . . , 2n and are listed in no particular order. The specification of any hole or triangle will have the form x1 y1 x2 y2 x3 y3 where each xi and yi will be to the nearest thousandth and |xi|, |yi| ≤ 200. No two holes will be congruent and no two triangles will be congruent. A value of n = 0 will terminate input.
For each test case, you should output the case number and then n lines as follows:
where t1a, t1b are the two triangles which fill hole 1, t2a, t2b are the two triangles which fill hole 2, etc. Always print the lower of the two numbers first on any line. Triangles should not be flipped over when filling a hole. Each test case will have a unique solution. Separate the output for each test case with a blank line. Note: when processing the triangles and checking for equality of lengths, angles or trigonometric values, you may assume that two items are equal if they differ by less than 0.01.
1 18.691 6.103 21.668 13.709 21.332 25.894 59.388 30.873 55.299 36.186 61.45 22.97 67.828 85.496 60.751 72.752 59.2 67.49 3 18.73 4.012 6.662 7.557 14.035 7.478 14.869 32.398 32.341 31.772 7.522 29.674 25.272 6.868 4.572 2.014 10.487 16.121 26.135 53.073 44.18 50.723 40.31 42.91 86.601 29.95 70.542 17.088 66.77 14.88 90.344 89.528 92.179 88.665 87.99 82.54 39.327 62.11 35.033 57.127 18.14 63.89 37.13 80.202 36.308 75.111 34.28 75.11 14.043 68.482 15.22 55.423 10.42 75.43 0
Case 1: Hole 1: 1, 2 Case 2: Hole 1: 3, 5 Hole 2: 2, 6 Hole 3: 1, 4