24957번 - Loop of Chocolate 스페셜 저지다국어

Let’s make sweets of a fancy shape that is a loop of chocolate.

Figure A.1. A loop of chocolate formed by a union of six spheres

The shape of a loop is formed by a union of a number of spheres of the same size, where every sphere intersects with exactly two others.

(a) Union of four spheres	(b) Four intersections of the four spheres in (a)
Figure A.2. A loop of chocolate formed by a union of four spheres

Your job is to write a program that, for given the size and the positions of spheres, computes the total volume of the union of the spheres, i.e., the amount of chocolate required for filling the loop formed by the union.

[Hints] Two spheres of the same radius $r$ intersect each other when the distance between their centers, $d$, is less than $2r$. The volume of the intersection is known to be $$\frac{2}{3}\pi (r - d/2)^2(2r+d/2)\text{.}$$

The volume of the sphere of radius $r$ is $4\pi r^3/3$.

The input consists of a single test case of the following format.

$\begin{align*}&n \, r \\ & x_1 \, y_1 \, z_1 \\ & \vdots \\ & x_n \, y_n \, z_n \end{align*}$

$n$ and $r$ are integers. $n$ is the number of spheres ($4 ≤ n ≤ 100$). All the spheres has the same radius $r$ ($2 ≤ r ≤ 100$). $(x_k, y_k, z_k)$ indicates the coordinates of the center of the $k$-th sphere ($k = 1, \dots , n$). All of $x_k$, $y_k$, and $z_k$ are integers between $-100$ and $100$, inclusive.

The $k$-th and the $k + 1$-th spheres intersect each other for $1 ≤ k < n$. The $1$-th and the $n$-th spheres also intersect. No other pairs of spheres intersect.

Output in a line the volume of the union of the spheres. Relative error of the output should be within $10^{-7}$.