[BZOJ1013][JSOI2008]球形空间产生器sphere 高斯消元

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1013

首先题目给出了定义$dist^2=sum_{i=1}^n(a_i-x_i)^2$。那我们假设有两个点$a$和$b$，用两个式子做差整理可得$$sum_{i=1}^n2*(a_i-b_i)*x_i=sum_{i=1}^na_i^2-b_i^2$$

那么我们把第1个点拿出来和其它n个点做差得出n个方程，就可以用高斯消元了。高斯消元大概就是每一次用一个方程与剩余的方程做差，消去一个未知数，这样做n-1次就可以得到解中的一个未知数，然后依次从最后回带进去，就可以把所有的未知数一个一个解出来。要注意的是为了保证精度误差尽可能小，所选择的拿去消元的方程，应该是我们要消的那个元的系数最大的那个方程。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
double a[15][15],l[15][15];
void Gauss(){
    for(int i=1;i<=n;i++){
        int t=i;
        for(int j=i+1;j<=n;j++)
            if(fabs(l[j][i])>fabs(l[t][i]))
                t=j;
        if(t!=i)
            for(int j=i;j<=n+1;j++)
                swap(l[i][j],l[t][j]);
        for(int j=i+1;j<=n;j++){
            double x=l[j][i]/l[i][i];
            for(int k=i;k<=n+1;k++)
                l[j][k]-=l[i][k]*x;
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=i+1;j<=n;j++)
            l[i][n+1]-=l[j][n+1]*l[i][j];
        l[i][n+1]/=l[i][i];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++){
        for(int j=1;j<=n;j++){
            scanf("%lf",&a[i][j]);
            if(i!=1){
                l[i-1][j]=2*(a[i][j]-a[1][j]);
                l[i-1][n+1]+=a[i][j]*a[i][j]-a[1][j]*a[1][j];
            }
        }
    }
    Gauss();
    for(int i=1;i<=n;i++){
        printf("%.3lf",l[i][n+1]);
        if(i!=n) putchar(' ');
    }
    return 0;
}