题目大意
在 \(n\) 维空间中，给定球面上的 \(n+1\) 个点的坐标，求球心的坐标。
解题思路
标签：高斯消元法
1. 问题转化
设球心坐标为 \((x_1, x_2, ..., x_n)\)，半径为 \(R\)。
对于球面上的每个点 \(P_i = (a_{i1}, a_{i2}, ..., a_{in})\)，有：
\[\sum_{k=1}^{n} (a_{ik} - x_k)^2 = R^2 \quad \text{(1)}
\]
这是一个含有 \(n+1\) 个未知数（\(x_1, x_2, ..., x_n\) 和 \(R^2\)）的二次方程组。
2. 消去二次项
考虑两个点 \(P_i\) 和 \(P_j\)，根据方程(1)有：
\[\sum_{k=1}^{n} (a_{ik} - x_k)^2 = \sum_{k=1}^{n} (a_{jk} - x_k)^2
\]
展开并移项：
\[\sum_{k=1}^{n} (a_{ik}^2 - 2a_{ik}x_k + x_k^2) = \sum_{k=1}^{n} (a_{jk}^2 - 2a_{jk}x_k + x_k^2)
\]
消去两边的 \(x_k^2\)，得到：
\[\sum_{k=1}^{n} (a_{ik}^2 - a_{jk}^2) = 2\sum_{k=1}^{n} (a_{ik} - a_{jk})x_k
\]
这是一个关于 \(x_k\) 的线性方程！
3. 构建线性方程组
用第 \(i\) 个点和第 \(i+1\) 个点构造方程（\(i=1\),\(2\),...,\(n\)），得到 \(n\) 个线性方程：
令：
\[系数矩阵C_{ik} = 2(a_{ik} - a_{(i+1)k})
\]
\[常数项b_i = \sum_{k=1}^n (a_{ik}^2 - a_{(i+1)k}^2)
\]
则方程组为：
\[\sum_{k=1}^{n} C_{ik}x_k = b_i, \quad i = 1, 2, ..., n
\]
这是一个 \(n\) 元一次线性方程组，可以用高斯消元法求解。
时间复杂度
- 构建方程组：\(O(n^2)\)
- 高斯消元：\(O(n^3)\)
- 总复杂度：\(O(n^3)\)
对于 \(n\) ≤ \(10\)，可以接受。
参考代码
#include <bits/stdc++.h>
using namespace std;double a[20][20]; // 存储点的坐标，a[i][j]表示第i个点的第j维坐标
double b[20]; // 线性方程组的常数项
double c[20][20]; // 线性方程组的系数矩阵
double d = 1e-9; // 精度控制，用于判断是否为0
int n;int main() {cin >> n;// 读入n+1个点的坐标for (int i = 1; i <= n + 1; i++)for (int j = 1; j <= n; j++)cin >> a[i][j];// 构建线性方程组// 用第i个点和第i+1个点构造第i个方程for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {c[i][j] = 2 * (a[i][j] - a[i + 1][j]);b[i] += a[i][j] * a[i][j] - a[i + 1][j] * a[i + 1][j];}}// 高斯消元法求解线性方程组for (int i = 1; i <= n; i++) {// 列主元消去法：寻找第i列中绝对值最大的元素for (int j = i; j <= n; j++) {if (abs(c[j][i]) > d) { // 找到非零主元// 交换第i行和第j行for (int k = 1; k <= n; k++)swap(c[i][k], c[j][k]);swap(b[i], b[j]);break; // 找到后就跳出}}// 消元：将第i列的其他行消为0for (int j = 1; j <= n; j++) {if (i == j) continue; // 跳过当前行// 计算消元系数double r = c[j][i] / c[i][i];// 对第j行进行消元for (int k = i; k <= n; k++)c[j][k] -= c[i][k] * r;b[j] -= b[i] * r;}}for (int i = 1; i < n; i++)printf("%0.3lf ", b[i] / c[i][i]);printf("%.3lf", b[n] / c[n][n]);return 0;
}