Astar

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2684
64-bit integer IO format: %I64d      Java class name: Main

Description

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.

Input

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.

Output

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

Sample Input

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

Sample Output

72
7

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .