eolymp
bolt
Try our new interface for solving problems
Problems

Convex area

Convex area

A \textbf{3}-dimensional shape is said to be \textit{convex} if the line segment joining any two points in the shape is entirely contained within the shape. Given a general set of points \textbf{X} in \textbf{3}-dimensional space, the \textit{convex hull} of \textbf{X} is the smallest convex shape containing all the points. For example, consider \textbf{X} = \{(\textbf{0}, \textbf{0}, \textbf{0}), (\textbf{10}, \textbf{0}, \textbf{0}), (\textbf{0}, \textbf{10}, \textbf{0}), (\textbf{0}, \textbf{0}, \textbf{10})\}. The convex hull of \textbf{X} is the tetrahedron with vertices given by \textbf{X}. Note that the tetrahedron contains the point (\textbf{1}, \textbf{1}, \textbf{1}), so even if this point were added to \textbf{X}, the convex hull would not change. Given \textbf{X}, your task is to find the surface area of the convex hull of \textbf{X}, rounded to the nearest integer. \textbf{NOTE:} The convex hull of any point set will have polygonal faces. For this problem, you may assume there will be at most \textbf{3} points in \textbf{X} on any face of the convex hull. \InputFile The input test file will contain multiple test cases, each of which begins with an integer \textbf{n} (\textbf{4} ≤ \textbf{n}\textit{ } ≤ \textbf{25}) indicating the number of points in \textbf{X}. This is followed by \textbf{n} lines, each containing 3 integers giving the \textbf{x}, \textbf{y} and \textbf{z} coordinate of a single point. All coordinates are between \textbf{−100} and \textbf{100} inclusive. The end-of-file is marked by a test case with \textbf{n}\textit{ } = \textbf{0} and should not be processed. \OutputFile For each test case, write a single line with the surface area of the convex hull of the given points. The answer should be rounded to the nearest integer (e.g., \textbf{2.499} rounds to \textbf{2}, but \textbf{2.5} rounds to \textbf{3}). \textbf{Hint} To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least \textbf{0.001} away from a decision boundary (i.e., you can assume that the area is never \textbf{2.4997}).
Time limit 1 second
Memory limit 64 MiB
Input example #1
5
0 0 0
10 0 0
0 10 0
0 0 10
1 1 1
9
0 0 0
2 0 0
2 2 0
0 2 0
1 1 2
1 1 -2
1 1 -1
1 1 0
1 1 1
0
Output example #1
237
18