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.

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 2ドルr$. 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}$.

제한

힌트