自动搬运

查看原文

来自洛谷，原作者为

	Zwaire 把一切不可能变为可能

搬运于2025-08-24 22:30:02，当前版本为作者最后更新于2022-04-06 18:58:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P7455 [THUSCH2017] 宇宙广播

本题解主要参考了 yww 神犇的题解。Link

题目描述：

给你 $n$ 个 $n$ 维空间的球，求这些球的公切面。保证不会无解或者有无穷多组解。

题目分析：

首先 $K= 2$ 只需要求两个圆的公切线就行了，注意题目里面不保证相离和半径不为 $0$ ，进行特判即可。

考虑 $K$ 较大的数据。

首先我们需要知道如何表示一个平面：

拿三维来举个例子 Link

其实前面代表着就是当前空间的法向量，最后一个常数表示到原点的距离。

这样的话我们可以进行类比一下，我们形式化的表示这个平面为:

$$\sum_{i=1}^{k} a_ix_i = d$$

我们假设 $\sum_{i=1}^Ka_i^2=1$。

其次我们需要知道如何求一个点到平面的距离公式：

还是拿三维举个例子 Link

那类比一下 $K$ 维，故点到平面距离公式可写成：

$$dist=\frac {\left|\sum _{i=1}^{K}a_ix_i - d\right|}{\sqrt{\sum_{i=1}^{K}a_i^2}} $$

那么对于每个球 $c$ 我们都可以得到方程：

$$\left|\sum_{i=1}^{K} a_ix_{c,i}-d\right| = r_c$$

由于 $K\leq 10$ 我们直接 状压/dfs 枚举绝对值的情况。对于每种情况，直接解方程，将 $a_i$ 表示成 $k_1d+k_2$ 的形式 ，将解得的 $a_i$ 带入 $\sum_{i=1}^{K}a_i^2 = 1$ 即可求得 $d$ 。

然后解出来这个平面的法向量，然后就可以根据这个求交点了。

有一个需要注意的点，直接算会有点问题，全都是 0，所以要稍微偏移一点。（奇怪的问题？yww 本人也没给出原因）

Code