Asteroids#521
Asteroid Collision Control Association (ACM) plans to conduct a controlled collision of two asteroids. The asteroids will be slowly brought together and will collide at negligible speed. ACM expects the asteroids to join and form a stable object.
Each asteroid has the form of a convex polyhedron. To maximize the experiment's chances of success, ACM wants to bring the asteroids together such that their centers of mass are as close as possible. To achieve this, ACM operators can rotate and move the asteroids independently before bringing them together.
Help ACM determine the minimal possible distance between the centers of mass that can be achieved.
For the purposes of calculating the center of mass, both asteroids are considered to have constant density.
The input file contains descriptions of two convex polyhedra.
The first line of each description contains an integer — the number of vertices of the polyhedron (4 \le n \le 60). The next lines contain three integers x_i, y_i, z_i each — the coordinates of the -th vertex of the polyhedron (-10^4 \le x_i, y_i, z_i \le 10^4). It is guaranteed that the given points are vertices of a convex polyhedron; in particular, no point lies in the convex hull of the other points. Each polyhedron is non-degenerate.
The given two polyhedra have no common points.
Output a single floating point number — the minimal achievable distance between the centers of mass of the asteroids. Your answer must be accurate to within 10^{-5}.
Example 1