问题描述:

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

输入:

第一行是一个整数$n(1<=N=10)$。接下来的$n+1$行,每行有$n$个实数,表示球面上一点的$n$维坐标。每一个实数精确到小数点后6位,且其绝对值都不超过20000。

输出:

有且只有一行,依次给出球心的$n$维坐标,两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。

思路:

这应该是比较裸的高斯消元了。球心到$n+1$个点距离相等,那么我们把距离当作常量就有$n+1$个方程。把常量减去后就剩下$n$个方程$n$个未知数,这时我们就可以用高斯消元了。

方程我就不列出来了(懒),然后因为方程保证有解,所以代码还是比较容易打的。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define MAXN 20
#define eps 1e-8
using namespace std;

int n;
double a[MAXN][MAXN], b[MAXN], c[MAXN][MAXN];

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]);
    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++)
    {
        for(int j=i; j<=n; j++)
            if(fabs(c[j][i])>eps)
            {
                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)
            {
                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;
            }
    }
    for(int i=1; i<n; i++) printf("%.3lf ", b[i]/c[i][i]);
    printf("%.3lf\n", b[n]/c[n][n]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注