Area
----

This problem was a test of your ability to do vector math.  Given a set of points in R^3,
your goal is to find the surface area of the 3D convex hull.  You are guaranteed that
all faces of the convex hull contain at most three point from your set.  At first glance,
the problem sounds extremely difficult because it sounds like you need a really complex
three-dimensional convex hull algorithm.

However, the maximum allowed number of points in the set is only 25, so it turns out the
following fairly simple solution suffices:

1) Consider all possible n choose 3 subsets of three points taken from our original set
   of n points.

2) If the 3 points define a plane (i.e., they are not colinear), then

   a) Check if all other points in the set lie on one side of the plane or the other.

   b) If there are points on only one side of the plane, then the triangle formed by the
      three points is a face of the convex hull, so compute its area.

The sum of the areas of all faces, then, is the surface area of the convex hull!

The first part of this problem is to visit the points in a way so as to ensure we don't
consider possible faces twice.  We can do this with a simple nested for loop:

   for i = 1 to n
     for j = i+1 to n
       for k = j+1 to n

The tricky part is to do the vector math required in step 2.  Let's go through this
carefully.  In the diagram below, A, B, and C are three points that we are considering
as a possible face for the convex hull.  You can think of A and C as being in the plane of the
screen and B is "farther away".  D and E are two points which lie to the left and right of the
plane, respectively.

                  B      A
                   o     O
                    ^    ^
            D        \   |
            *        v\  |u            
                       \ |
                        \|             * E
         <---------------O C
                 w

In this diagram, the vectors from C to each of the points A and B are given by

    u = A-C
    v = B-C

Then,

    w = u x v

is the vector which is orthogonal to both u and v (remember cross products from linear algebra?).
That is, w is a vector which is "normal" to the plane formed by A, B, and C.  (If you remember
the right-hand-rule for cross products, then you'll know that w points to the left---your thumb 
points in the direction of u, your pointer finger points in the direction of v, and your
middle finger points in the direction of the cross product, w.)

 +-----------------------------------------------------------------------------------------------+
 |                                                                                               |
 |  LINEAR ALGEBRA REMINDER:  To compute the cross product of u = (u1,u2,u3) and v = (v1,v2,c3), |
 |    write                                                                                      |
 |                                                                                               |
 |         | i   j   k  |                                                                        |
 |         | u1  u2  u3 | = i(u2*v3-u3*v2) + j(u3*v1-u1*v3) + k(u1*v2-u2*v1)                     |
 |         | v1  v2  v3 |                                                                        |
 |                                                                                               |
 |     So, w = (w1, w2, w3) = u x v where                                                        |
 |                                                                                               |
 |         w1 = u2*v3-u3*v2                                                                      |
 |         w2 = u3*v1-u1*v3                                                                      |
 |         w3 = u1*v2-u2*v1.                                                                     |
 |                                                                                               |
 +-----------------------------------------------------------------------------------------------+
    
So now we have a vector w which is normal to the plane formed by A, B, and C.  How do we tell
on which side of the plane a point D lies?  If we define

    z(D) = D-C

then

    z(D) * w  (dot product)

 +-----------------------------------------------------------------------------------------------+
 |                                                                                               |
 |  LINEAR ALGEBRA REMINDER:  The dot product of u = (u1,u2,u3) and v = (v1,v2,c3) is            |
 |                                                                                               |
 |         u*v = u1*v1 + u2*v2 + u3*v3                                                           |
 |                                                                                               |
 +-----------------------------------------------------------------------------------------------+

is positive whenever D is on the same side of the plane as C+w; i.e., z(D) * w is positive if w is
pointing away from the plane in the direction of D.  (Note: You could also define z(D) = D-A or 
z(D) = D-B and the above would still work -- why?).  Thus, A, B, and C form a face of the convex hull if
and only if all other points in the set are on the same side of plane as C+w; i.e., if z(D) * w is
positive for all other points D in the set, or negative for all other points D in the set.

OK, so now that we have a test for checking if the triangle A,B,C is a face of the convex hull,
how do we compute the area?  It turns out that

   area of triangle ABC = ||w|| / 2.

 +-----------------------------------------------------------------------------------------------+
 |                                                                                               |
 |  LINEAR ALGEBRA REMINDER:  The norm ||u|| of a vector u = (u1,u2,u3) is                       |
 |                                                                                               |
 |         ||u|| = sqrt (u*u) = sqrt(u1*u1+u2*u2+u3*u3)                                          |
 |                                                                                               |
 +-----------------------------------------------------------------------------------------------+

That's it!