BZOJ 1013
题意：给定$n$维空间一个球面上$n+1$个点的坐标，求球心坐标。
提示：球心是到球面上任意一点距离都相等的点。
根据提示，我们设$a_{i,j}$为点$i$的第$j$维坐标，$x_{j}$为球心$j$维坐标，则对于每个点$i$ 有
$$
\sum_{j=1}^n (a_{i,j}-x_{j})^2=C
$$
其中$C$为一个常数。这个方程是二元$n$次方程，不好解，我们采用邻项相减的方法，使其变为一维以及消除$C$，则
$$
\sum_{j=1}^n(a_{i+1,j}-x_{j})^2 - (a_{i,j}-x_{j})^2=0
$$
化简，将$x_j$移到左边，得
$$
\sum_{j=1}^n 2x_j(a_{i,j}-a_{i+1,j})=\sum_{j=1}^n(a_{i,j}^2-a_{i+1,j}^2)
$$
则可以构造矩阵高斯消元。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 15;
const db eps = 1e-12;
int n;
db a[MAXN][MAXN], c[MAXN][MAXN], b[MAXN];
// c, b 为消元矩阵
void clean() {
ms(b, 0);
}
int solve() {
clean();
scanf("%d", &n);
for (int i = 1; i <= n + 1; ++i)
for (int j = 1; j <= n; ++j) scanf("%lf", &a[i][j]);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
c[i][j] = 2.0 * (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) { // 处理 xi[i] 的系数
for (int j = i; j <= n; ++j) { // 从后面没处理的行找 xi[i] 系数不为 0 的行交换
if (c[j][i] > eps) {
swap(b[i], b[j]);
for (int k = 1; k <= n; ++k) swap(c[i][k], c[j][k]);
}
}
if (fabs(c[i][i]) < eps) continue ; // 注意
for (int j = 1; j <= n; ++j) { // 消去其他方程 xi[i] 的系数
if (i == j) continue ;
db rat = c[j][i] / c[i][i];
for (int k = 1; k <= n; ++k) c[j][k] -= rat * c[i][k];
b[j] -= rat * b[i];
}
}
for (int i = 1; i < n; ++i) printf("%.3lf ", b[i] / c[i][i]);
printf("%.3lf\n", b[n] / c[n][n]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
