Programming Assignment 6 - Tangrams

Advanced Programming II, Fall 2002

Due Date

This assignment is due by 2:00 p.m. on Tuesday, 3 December.

See the assignment turn-in page (last modified on 4 March 2002) for instructions on turning in your assignment.

Background

The tangram puzzle consists of 7 pieces (called tans):

tangram pieces

The objective of the puzzle is to arrange all seven tans to form a shape described only in outline. For example, the simple puzzle

a simple tangram puzzle

has the solution

the puzzle solved

Problem

Write a program that solves tangram puzzles. Your program should read from std-in a sequence of floating-point numbers that are interpreted as the x, y coordinates of vertices on the outline of a puzzle in either clockwise or counter-clockwise order starting from an arbitrary vertex on the outline. The last point read is adjacent to the first point read.

Your program should output the solution to the input puzzle or impossible if the puzzle can't be solved. If the puzzle has a solution, the tans should be output one per line, with each tan being output as a sequence of vertices in either clockwise or counter-clockwise order starting from an arbitrary vertex on the tan. The tan vertices should be given in the coordinate system defined by the input puzzle.

For example, the following input describes the square puzzle given in the Background Section: 

-1 -1 -1 3 3 3 3
-1

The solution to this puzzle would be output as 

-1 -1 -1 3 1 1
-1 3 3 3 1 1
-1 -1 0 0 2 0 1 -1
3 1 1 -1 3 -1
0 0 2 0 1 1
2 0 3 1 2 2 1 1
3 3 2 2 3 1

The input data describes one continuous outline; the shape will not consists of separate pieces. Each input shape is solid; it will have no holes.

This page last modified on 27 November 2002.