题目分析

已知 $n+1$ 个 $n$ 维球面上的点，求球心坐标。

---

数学推导

设球心为 $(x_1, x_2, \dots, x_n)$，球面上两点 $P_i$ 和 $P_j$ 到球心距离相等：

$$\sum_{k=1}^n (a_{i,k} - x_k)^2 = \sum_{k=1}^n (a_{j,k} - x_k)^2 $$

展开消去平方项得线性方程组：

$$\sum_{k=1}^n 2(a_{j,k} - a_{i,k})x_k = \sum_{k=1}^n (a_{j,k}^2 - a_{i,k}^2) $$

---

算法步骤

1. 构造线性方程组

用第 $1$ 个点分别与后面 $n$ 个点建立 $n$ 个方程：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++)
        mp[i][j] = 2 * (a[i][j] - a[i + 1][j]);
    for (int j = 1; j <= n; j++)
        mp[i][n + 1] += pow(a[i][j], 2) - pow(a[i + 1][j], 2);
}

2. 高斯消元求解

• 选主元避免除零
• 消元形成上三角矩阵
• 回代求解

for (int i = 1; i <= n; i++) {
    int r = i;
    for (int j = i + 1; j <= n; j++)
        if (fabs(mp[j][i]) > fabs(mp[r][i])) r = j;
    swap(mp[i], mp[r]);
    
    for (int j = 1; j <= n; j++) {
        if (i == j) continue;
        double div = mp[j][i] / mp[i][i];
        for (int k = i; k <= n + 1; k++)
            mp[j][k] -= mp[i][k] * div;
    }
}

3. 输出结果

直接输出对角化后的解：

for (int i = 1; i <= n; i++)
    cout << fixed << setprecision(3) << mp[i][n + 1] / mp[i][i] << ' ';

---

复杂度分析

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$

在 $n \leq 10$ 时非常高效。

---

样例验证

输入：

2
0.0 0.0
-1.0 1.0
1.0 0.0

计算过程：

• 构造 $2$ 个方程
• 高斯消元求解
• 输出：0.500 1.500

与样例一致。

该解法通过几何性质转化为线性方程组，用高斯消元精确求解球心坐标。