[Wannafly冬令营2018Day2]Cosmic Cleaner

在一片小行星带里有 $n$ 颗小行星，它们在万有引力的作用下绕着一颗行星旋转。在这一刻时，它们之间不存在碰撞的情况。一位清洁工奉命前来清理这颗行星，Ta 会动用某种先进技术使这颗行星顷刻间从宇宙中消失，任何距离这颗行星的中心在一定范围内的事物都会在一瞬间被清除。假设这些天体都是完整的球体，你能计算出清除的区域里有多少体积的事物原本属于这些小行星吗？

注意，这些天体在此刻满足两两不存在交集的条件。

下图是对样例的解释，其中清理区域是标记为红色的球体内部，而小行星则被依次标记为橙色、蓝色和绿色。

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。随后的内容是各组测试数据。对于每组测试数据：

第一行包含一个整数 $n$。

接下来的 $n$ 行里，每行包含四个整数 $x, y, z$ 和 $r$，表示有一颗中心位于 $(x, y, z)$、半径为 $r$ 的小行星。

最后一行包含四个整数 $x', y', z'$ 和 $r'$，表示行星的中心位于 $(x', y', z')$，而清洁工的清理半径为 $r'$（一个大于该行星半径的值）。

$1 \leq T \leq 6000$
$1 \leq n \leq 100$
$-10^3 \leq x, y, z, x', y', z' \leq 10^3$
$1 \leq r, r' \leq 10^3$

对于每组测试数据，输出一行Case #x: y，其中x是测试数据的编号（从 $1$ 开始编号），y是这组数据的答案，要求相对误差或绝对误差不超过 $10^{-6}$。

严格来讲，如果你的答案是 $a$，而标准答案是 $b$，那么当 $\frac{|a - b|}{\max{1, |b|}} \leq 10^{-6}$ 时你的答案会被认为是正确的。

样例输入 1

样例输出 1

Case #1: 142.76246874761383764962

C1951 [Wannafly冬令营2018Day2]Cosmic Cleaner

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示