Description
有一个球形空间产生器能够在\(n\)维空间中产生一个坚硬的球体.现在,你被困在了这个\(n\)维球体中,你只知道球面上\(n+1\)个点的坐标,你需要以最快的速度确定这个\(n\)维球体的球心坐标,以便于摧毁这个球形空间产生器.
Input
第一行是一个整数\(n(1\leq{N}\leq10)\).
接下来的\(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
- 球心:到球面上任意一点距离都相等的点.
- 距离:设两个\(n\)为空间上的点\(A,B\)的坐标为\((a_1,a_2,\dots,a_n),(b_1,b_2,\dots,b_n)\)，则\(AB\)的距离定义为:\(dist=\sqrt{(a_1-b_1)^2 +(a_2-b_2)^2+\dots+(a_n-b_n)^2}\).
Solution
设球心坐标为\((x_1,x_2,\dots,x_n)\),
球面上点的坐标为\((y_{1,i},y_{2,i},\dots,y_{3,i})\),
则\(\sum(y_{i,j}-x_i)^2=C\).
所以\(\sum(y_{i,j}-x_i)^2=\sum(y_{i,j+1}-x_i)^2\).
因为\(\sum(y_{i,j}-x_i)^2=\sum(y_{i,j}^2-2\times{y_{i,j}}\times{x_i}+x_i^2)\)
所以\(\sum(y_{i,j}^2-2\times{y_{i,j}}\times{x_i}+x_i^2)=\sum(y_{i,j+1}^2-2\times{y_{i,j+1}}\times{x_i}+x_i^2)\)
所以\(\sum(2\times{x_i}\times(y_{i,j+1}-y_{i,j}))=\sum(y_{i,j+1}^2-y_{i,j}^2)\).
就可以用高斯消元求解了.
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 20
#define F 1e-13
using namespace std;
double a[N][N],b[N][N],ans[N];
int n;
inline void gauss(){
double tmp;
for(int i=1;i<=n;++i){
if(fabs(a[i][i])<eps)
for(int j=i+1;j<=n;++j)
if(a[j][i]){
for(int k=i;k<=n+1;++k)
swap(a[i][k],a[j][k]);
break;
}
for(int j=1;j<=n;++j)
if(j!=i&&fabs(a[j][i])>0){
tmp=a[j][i]/a[i][i];
for(int k=i;k<=n+1;++k)
a[j][k]=a[j][k]-tmp*a[i][k];
}
}
for(int i=1;i<=n;++i)
ans[i]=a[i][n+1]/a[i][i];
}
inline void Aireen(){
scanf("%d",&n);
for(int i=1;i<=n+1;++i){
for(int j=1;j<=n;++j)
scanf("%lf",&b[i][j]);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
a[i][j]=2.0*(b[i][j]-b[i+1][j]);
a[i][n+1]+=pow(b[i][j],2)-pow(b[i+1][j],2);
}
gauss();
for(int i=1;i<n;++i)
printf("%.3lf ",ans[i]);
printf("%.3lf\n",ans[n]);
}
int main( ) {
freopen("sphere.in","r",stdin);
freopen("sphere.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
2017-03-06 20:28:54