Description
有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器。
Input
第一行是一个整数,n。接下来的n+1行,每行有n个实数,表示球面上一点的n维坐标。每一个实数精确到小数点后6位,且其绝对值都不超过20000。
思路:可以列出方程,由于从球上每个点到球心的距离相等,所以两两相减可以刚好列出n个方程,接下来就可以高斯消元了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
double a[][],f[],t,eps=1e-;
int n;
double sqr(double x){
return x*x;
}
void gauss(){
int now=,to;double t;
for (int i=;i<=n;i++){
for (to=now;to<=n;to++) if (fabs(a[to][i])>eps) break;
if (to>n) continue;
if (to!=now)
for (int j=;j<=n+;j++)
std::swap(a[to][j],a[now][j]);
t=a[now][i];
for (int j=;j<=n+;j++) a[now][j]/=t;
for (int j=;j<=n;j++)
if (j!=now){
t=a[j][i];
for (int k=;k<=n+;k++)
a[j][k]-=t*a[now][k];
}
now++;
}
}
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%lf",&f[i]);
for (int i=;i<=n;i++){
for (int j=;j<=n;j++){
scanf("%lf",&t);
a[i][j]=*(t-f[j]);
a[i][n+]+=sqr(t)-sqr(f[j]);
}
}
gauss();
for (int i=;i<=n-;i++)
printf("%.3f ",a[i][n+]);
printf("%.3f\n",a[n][n+]);
}