Bikpik Colony

shibly Replay of Cybernauts NPC...
Limits 1s, 1.0 GB

Bikpiks are very small aliens. Day by day they are becoming very dangerous for human being. They live at some colonies in space. The colonies are so small, you can assume a colony as a point in 3D cartesian coordinate. It is guaranteed that all colonies are coplanar (a set of points in space are coplanar if there exists a geometric plane that contains them all).

Captain Gomo is assigned to save the earth from Bikpiks. He decided to destroy all the Bikpik colonies. To destroy the colonies:

1. He encloses a volume with a particular cover.
2. The colonies inside the volume which are at least **D** units away from the cover, are destroyed. Note that, there might be a point inside the volume which is not **D** units away, in that case, it will not be destroyed. Also, the cover is not reusable. He repeats this process until all the colonies are destroyed. 

The ingredients of the cover are costly. So he wants to minimize the total surface area required for the covering task.


The first line of the input contains an integer T (T ≤ 25), the number of test sets.

Each set of input starts with line containing two integers N (N ≤ 12) and D (1 ≤ D ≤ 103). N denotes the number of Bikpik colonies. Following N line contain three space separated integers X, Y and Z (−103 ≤ X, Y, Z ≤ 103) denoting three coordinates of each colonies.

Each test set starts with a blank line.


For each case, print the minimum surface area in single line. Error less than 10-4 will be ignored.



1 10
3 4 -5

4 10
0 0 0
0 10 0
10 0 0
999 999 0

In second test case, he covers up first three colonies together and remaining one in separately.


Login to submit.



100% Solution Ratio
ovis96Earliest, Apr '18
steinumFastest, 0.0s
ovis96Lightest, 131 kB
steinumShortest, 3955B
Toph uses cookies. By continuing you agree to our Cookie Policy.