Catching butterflies - MarisaOJ: Marisa Online Judge

Catching butterflies

Time limit: 1000 ms
Memory limit: 256 MB
Marisa wandered deep into the magical forest, where enchanted butterflies flitted through the trees. She wanted to catch them all, but simply trapping them in a cage wouldn't work. Instead, she needed to cast a magical barrier that would perfectly enclose the butterflies, using the least amount of power. The amount of magical energy required is proportional to the volume of the barrier. To find the most efficient barrier, Marisa realized she needed the convex hull — the smallest 3D shape that could contain all the butterflies. Help Marisa determine the convex hull's volume and surface area, so she could calculate how much magic she would need to catch them all, given that each butterfly can be represented as a point in space. ### Input - The first line consists of an integer $t$ - the number of test cases. - The next $t$ groups of lines come under the form of: - The first line consists of an integer $n$ - the number of butterflies. - The next $n$ lines each contain three real numbers $x_i, y_i, z_i$ corresponding to the coordinates of the $i$-th butterfly. ### Output Print $t$ lines, each line containing the surface area and the volume of the magical barrier. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-2}$. In other words, your answer, $x$, will be compared to the correct answer, $y$. If $|x-y| < 10^{-2}$, then your answer will be considered correct. ### Constraints - $1 \le t \le 10$. - $1 \le n \le 1000$. - $-10.0 \le x_i,y_i,z_i \le 10.0$. ### Example Input: ``` 1 10 0.00000 0.00000 0.00000 1.00000 0.00000 0.00000 0.00000 1.00000 0.00000 0.00000 0.00000 1.00000 1.00000 1.00000 0.00000 1.00000 0.00000 1.00000 0.00000 1.00000 1.00000 1.00000 1.00000 1.00000 0.50000 0.50000 0.50000 0.66666 0.77777 0.88888 ``` Output: ``` 6.0000 1.0000 ```