YbtOJ 894「高斯消元」高维寻点
题目链接：YbtOJ #894
小 A 有一个 $m$ 维空间。在这个空间中有 $n$ 个特殊点，其中第 $i$ 个特殊点 $p_i$ 的坐标为 $(x_{i,1},x_{i,2},\cdots,x_{i,m})$。
他希望找到这个 $m$ 维空间中的一个点 $P$，使得 $\max_{i=1}^n\operatorname{dist}(P,p_{i})$ 最小。
提示：$m$ 维空间中的两点 $(A_1,A_2,\cdots,A_m),(B_1,B_2,\cdots,B_m)$ 间的距离为 $\sqrt{\sum_{i=1}^m(A_i-B_i)^2}$。
$1\le n\le 20000$，$1\le m\le5$，$0\le$ 所有坐标 $\le10^4$。
Solution
首先二维最小覆盖圆的求法：
首先我们枚举一个点 $p_i$，如果它不在原本前 $i-1$ 个点的最小覆盖圆内，就必然在当前前 $i$ 个点的最小覆盖圆上。因此我们重构最小覆盖圆，由于初始只能确定这一个点在最小覆盖圆上，所以令此时的最小覆盖圆的圆心为当前点，半径为$0$。
然后我们再在 $[1,i)$ 中枚举点 $p_j$，如果它不在当前的最小覆盖圆内，同理我们可以确定它在新的最小覆盖圆上，那么我们就能确定两个点。所以令此时的最小覆盖圆的圆心为这两个点构成线段的中点，半径就是这两点间距离的一半。
同理继续在 $[1,j)$ 中枚举点 $p_k$，如果它不在当前的最小覆盖圆内，就令新的最小覆盖圆为这三个点的最小外接圆（其实之前两种情况也都是特殊的最小外接圆）。
这个做法看似暴力，但实际上可以利用 随机增量法 来使复杂度正确。即将数据随机打乱。
可以证明是 $O(N)$ 的。
那么高维的只需要解决如何求最小外接圆。
令 $\vec Q_i=q_i-q_t$，设圆心 $O=q_t+\sum_{i=1}^{t-1}\lambda_i\vec Q_i$。
由于 $\text{dist}(A,B)=\sqrt{(A-B)^2}$（这里的平方指自己与自己做点乘），因此可以对于每个 $k\in[1,t)$ 列出方程：
$$
(\sum_{i=1}^{t-1}\lambda_i\vec Q_i)^2=(\sum_{i=1}^{t-1}\lambda_i\vec Q_i-\vec Q_k)^2
$$
拆平方移个项即可得到：
$$
\sum_{i=1}^{t-1}2(\vec Q_i\cdot \vec Q_k)\lambda_i=(\vec Q_k)^2
$$
用高斯消元解个方程即可。
Code
1 |
|