Description
有一个球形空间产生器能够在 n 维空间中产生一个坚硬的球体现在, 你被困在了这个 n 维球体中, 你只知道球
面上 n+1 个点的坐标, 你需要以最快的速度确定这个 n 维球体的球心坐标, 以便于摧毁这个球形空间产生器
Input
第一行是一个整数 n(1<=N=10) 接下来的 n+1 行, 每行有 n 个实数, 表示球面上一点的 n 维坐标每一个实数精确到小数点
后 6 位, 且其绝对值都不超过 20000
Output
有且只有一行, 依次给出球心的 n 维坐标 (n 个实数), 两个实数之间用一个空格隔开每个实数精确到小数点
后 3 位数据保证有解你的答案必须和标准输出一模一样才能够得分
- Sample Input
- 2
- 0.0 0.0
- -1.0 1.0
- 1.0 0.0
- Sample Output
- 0.500 1.500
- HINT
提示: 给出两个定义: 1 球心: 到球面上任意一点距离都相等的点 2 距离: 设两个 n 为空间上的点 A, B
的坐标为 (a1, a2, , an), (b1, b2, , bn), 则 AB 的距离定义为: dist = sqrt( (a1-b1)^2 + (a2-b2)^2 +
+ (an-bn)^2 )
列出距离式子 (设球心坐标 x, 球上 2 个点 p,q):
- $\sum_{i}^{n}(p_i-x_i)^2=r^2$
- $\sum_{i}^{n}(q_i-x_i)^2=r^2$
两式相减, 就可以得到一个一次线性方程
构造出 n 个方程, 高斯消元
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- double a[51][51],p[51][51];
- int n;
- void guass()
- {int i,j,k,now;
- for (i=1;i<=n;i++)
- {
- now=i;
- for (j=i+1;j<=n;j++)
- if (fabs(a[now][i])<fabs(a[j][i]))
- now=j;
- for (j=i;j<=n+1;j++)
- swap(a[i][j],a[now][j]);
- for (j=i+1;j<=n+1;j++)
- a[i][j]/=a[i][i];
- a[i][i]=1;
- for (j=i+1;j<=n;j++)
- {
- for (k=i+1;k<=n+1;k++)
- {
- a[j][k]-=a[j][i]*a[i][k];
- }
- a[j][i]=0;
- }
- }
- for (i=n;i>=1;i--)
- {
- for (j=i+1;j<=n;j++)
- {
- a[i][n+1]-=a[i][j]*a[j][n+1];
- a[i][j]=0;
- }
- a[i][n+1]/=a[i][i];
- a[i][i]=1;
- }
- }
- int main()
- {int i,j;
- cin>>n;
- for (i=1;i<=n+1;i++)
- {
- for (j=1;j<=n;j++)
- scanf("%lf",&p[i][j]);
- }
- for (i=2;i<=n+1;i++)
- {
- for (j=1;j<=n;j++)
- {
- a[i-1][j]=p[i][j]-p[i-1][j];
- a[i-1][n+1]+=p[i][j]*p[i][j]-p[i-1][j]*p[i-1][j];
- }
- a[i-1][n+1]/=2.0;
- }
- guass();
- printf("%.3lf",a[1][n+1]);
- for (i=2;i<=n;i++)
- printf("%.3lf",a[i][n+1]);
- }
来源: http://www.bubuko.com/infodetail-2503670.html