题目大意

有$n+1$个保证在同一个球面上的点，给出他们的$n$维坐标，求球心坐标

数据范围

$1\leqslant n\leqslant 10$

每一个坐标都是实数，精确到小数点后6位，且其绝对值都不超过20000

题解

我们设球心为$X(x_1,x_2,...,x_n)$

假设有两点$A(a_1,a_2,...,a_n)$和$B(b_1,b_2,...,b_n)$

根据距离公式，我们可以得到两个方程

$(x_1-a_1)^2+(x_2-a_2)^2+...+(x_n-a_n)^2=r^2$……①

$(x_1-b_1)^2+(x_2-b_2)^2+...+(x_n-b_n)^2=r^2$……②

这些方程都是二次的，无法使用高斯消元，但是我们可以做一些处理，①-②可得

$(a_1-b_1)x_1+(a_2-b_2)x_2+...+(a_n-b_n)x_n=[(a_1^2-b_1^2)+(a_2^2-b_2^2)+...+(a_n^2-b_n^2)]/2$

然后就可以使用高斯消元来做题了

高斯消元的步骤

1. 把方程组转换成增广矩阵

2. 在消元以前，为了减小误差，每次取当前列对应的系数最大的一行，和当前行交换

3. 将当前行之后的每一行的当前列对应的系数处理归零，也就是消元

4. 消元完毕之后，从其中一个解推出全部解，有些题需要判断解的的情况

高斯消元的学习要感谢

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Ford(i,r,l) for(int i=r;i>=l;i--)
using namespace std;

int n;
double r[25],a[25][25],ans[25];
inline double sqr(double x){return (double)x*x;}

int main(){
    scanf("%d",&n);
    For(i,1,n) scanf("%lf",&r[i]);
    For(i,1,n){
        For(j,1,n){
            double x;scanf("%lf",&x);
            a[i][j]=r[j]-x;
            a[i][n+1]+=sqr(r[j])-sqr(x);
        }
        a[i][n+1]/=2;
    }
    For(i,1,n){
        int k=0;
        For(j,i,n)
            if (fabs(a[j][i])>fabs(a[k][i])) k=j;
        For(j,1,n+1) swap(a[i][j],a[k][j]);
        For(j,i+1,n){
            double x=-a[j][i]/a[i][i];
            For(p,i,n+1) a[j][p]+=a[i][p]*x;
        }
    }
    Ford(i,n,1){
        Ford(j,n,i+1) a[i][n+1]-=a[i][j]*ans[j];
        ans[i]=a[i][n+1]/a[i][i];
    }
    For(i,1,n) printf("%.3lf%c",ans[i],i==n?'\n':' ');
    return 0;
}