Astar

A 3-dimensional shape is said to be convex if the line segment joining any two points in the shape is entirely contained within the shape. Given a general set of points X in 3-dimensional space, the convex hull of X is the smallest convex shape containing all the points.
For example, consider X = {(0, 0, 0), (10, 0, 0), (0, 10, 0), (0, 0, 10)}. The convex hull of X is the tetrahedron with vertices given by X.

Given X, your task is to find the girth of the convex hull of X, rounded to the nearest integer.

You may assume there will be at most 3 points in X on any face of the convex hull.

The input test file will contain multiple test cases, each of which begins with an integer n (4 ≤ n ≤ 25) indicating the number of points in X. This is followed by n lines, each containing 3 integers giving the x, y and z coordinate of a single point. All coordinates are between −100 and 100 inclusive. The end-of-file is marked by a test case with n = 0 and should not be processed.

For each test case, write a single line with the girth of the convex hull of the given points. The answer should be rounded to the nearest integer

5
0 0 0
10 0 0
0 10 0
0 0 10
1 1 1

4
0 0 0
1 0 0
0 1 0
0 0 1
0

72
7

WhereIsHeroFrom

ZJFC 2009-3 Programming Contest