原题连接
更好的阅读体验

题目描述

有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。

现在，你被困在了这个$n$维球体中，你只知道球面上$n+1$个点的坐标，你需要以最快的速度确定这个$n$维球体的球心坐标，以便于摧毁这个球形空间产生器。

输入格式
第一行是一个整数$n$。

接下来的$n+1$行，每行有$n$个实数，表示球面上一点的n维坐标。

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

输出格式
有且只有一行，依次给出球心的n维坐标（n个实数），两个实数之间用一个空格隔开。

每个实数精确到小数点后3位。

数据保证有解。

数据范围
$1≤n≤10$

样例

输入样例：
2
0.0 0.0
-1.0 1.0
1.0 0.0
输出样例：
0.500 1.500

高斯消元

超级讨厌这种数学题目,欺负蒟蒻我latex写不好,注意以下latex一些是数学公式生成器生成的.

对于一个球体而言,所有点到球心的距离相等,所以只需要求出一个点$(x_1,x_2,…,x_n)$使得满足$\sum^{n}_{j=0}\left(a_{i,j}-x_{j}\right) ^{2}=C$

记住C是常数,$i\in \left[ 1,n+1\right]$ 那么这个方程组是由$n+1$个$n$元二次方程,然后我们同时消去C.$\sum ^{n}_{j=1}( a_{i,j}^2 -a_{i+1,j}^2 -2x_{j}\left( a_{i,j}-a_{i+1,j},\right)) (i=1,2,3,\ldots ,n)$

我们再把变量放左边,常数放右边.

$\sum ^{n}_{j=1}2\left( a_{i,j}-a_{i+1,j}\right) x_{j} = \sum ^{n}_{j=1}\left( a_{i,j}^{2}-a_{i+1,j}^{2}\right) (i=1,2,3,\ldots ,n)$

然后我们就可以开始愉快地高斯消元了.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,i,j;
double a[21][21],b[21],c[21][21];
inline int work()
{
    for(i=1;i<=n;i++)
    {
        for(j=i;j<=n;j++)
            if (fabs(c[j][i])>1e-8)
            {
                for (int k=1;k<=n;k++)
                    swap(c[i][k],c[j][k]);
                swap(b[i],b[j]);
            }
        for(int j=1;j<=n;j++)
        {
            if (i==j)
                continue;
            double rate=c[j][i]/c[i][i];
            for(int k=i;k<=n;k++)
                c[j][k]-=c[i][k]*rate;
            b[j]-=b[i]*rate;
        }
    }
}
inline void init()
{
    cin>>n;
    for(i=1;i<=n+1;i++)
        for(j=1;j<=n;j++)
            cin>>a[i][j];
    for(i=1;i<=n;i++)
        for(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];
        }
}
inline void out()
{
    for(int i=1;i<=n;i++)
        printf("%.3lf ",b[i]/c[i][i]);
}
int main()
{
    init();
    work();
    out();
    return 0;
}