Lowest Pyramid
Time limit30sMemory limit128 MB
Given an integer-coordinate base triangle, choose integer-coordinate apex points for its unfolded net so the folded tetrahedron has minimum positive height, or report impossibility.
- Level
Hard9 of 10
- Topics
- Geometry, Math, Brute force
- Solved
- No attempts yet
Problem
You want to build a triangular pyramid (a tetrahedron) out of a sheet of grid craft paper. Its base and its three lateral faces are all triangles. On the paper you draw the base triangle together with the three lateral triangles, each attached to one side of the base. You then cut along the six outer edges, fold the paper up along the three sides of the base, and assemble it into a pyramid.
Given the coordinates of the three vertices of the base, you must choose the coordinates of the remaining three vertices (the apex of each lateral face). The - and -coordinates of all six vertices must be integers between and inclusive. Your goal is to minimize the height of the assembled pyramid subject to these conditions.
Input
The input consists of several datasets. Each dataset is a single line of the following form.
X0 Y0 X1 Y1 X2 Y2
All six values are integers between and inclusive. , , are the coordinates of the three vertices of the triangular base, given in counterclockwise order.
The end of the input is indicated by a line containing six zeros separated by single spaces (0 0 0 0 0 0).
Output
For each dataset, print the answer on its own line.
If you can choose three points , , whose coordinates are all integers between and inclusive such that the four triangles ––, ––, –– and –– do not overlap one another in the -plane, and they can be folded up into a triangular pyramid of positive (non-zero) height, print the minimum height among all such pyramids. If no such pyramid exists, print .
Whenever the height is positive it is guaranteed to be at least . Print the height to six significant figures (as by C's %g): for example print 2 for a height of and 1.49666 for a height of .