This page is still under construction.

Parts of this page are still being built. What you see may change.

Exportation in Space

Time limit2sMemory limit512 MB

Summary
Given N points in 3D, find the surface area of their convex hull, printed to three decimals.
Level

Medium7 of 10

Topics
Geometry, Implementation, Brute force, Math
Solved
No attempts yet

Problem

In an era of space travelling, Mr. Jonathan A. Goldmine exports a special material named "Interstellar Condensed Powered Copper". A piece of it consists of several spheres floating in the air. A strange force acts between the spheres so that their relative positions do not change. If you move one of them, all the others follow it.

Example of ICPC (left: bare, right: shielded)

To transport ICPCs between planets, each piece needs to be shielded from cosmic rays. It breaks when hit by strong cosmic rays. Mr. Goldmine needs to wrap each ICPC piece with an anti-cosmic-ray shield, a paper-like material that blocks all cosmic rays. To save cost, he wants to know the minimum area of shield he needs to wrap an ICPC piece.

Note that he cannot put the shield between the spheres of an ICPC because it affects the force between the spheres. So the only way to shield it is to wrap the whole ICPC piece with the shield.

Mr. Goldmine asked you, an experienced programmer, to calculate the minimum area of shield for each material.

You can assume that each sphere in an ICPC piece is a point, and you can ignore the thickness of the shield.

Input

Each file consists of one test case, which has the information of one ICPC piece. A test case starts with a line with an integer N (4 ≤ N ≤ 50), denoting the number of spheres in the piece of the test case. Then N lines follow. The i-th line of them describes the position of the i-th sphere. It has 3 integers xi, yi and zi (0 ≤ x, y, z ≤ 100), separated by a space. They denote the x, y and z coordinates of the i-th sphere, respectively.

It is guaranteed that there are no data all of whose spheres are on the same plane, and that no two spheres in a data are on the same coordinate.

Output

For each input, print the area of the shield Mr. Goldmine needs. The output value should be printed with three digits after the decimal point, and should not contain an error greater than 0.001.

Examples2

  1. Example 1

    Input
    4
    0 0 0
    0 0 1
    0 1 0
    1 0 0
    
    Expected output
    2.366
    
  2. Example 2

    Input
    8
    0 0 0
    0 0 1
    0 1 0
    0 1 1
    1 0 0
    1 0 1
    1 1 0
    1 1 1
    
    Expected output
    6.000