P7455 [THUSCH2017] 宇宙广播

· · 题解

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