球形空间产生器

题目描述

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

给出两个定义:

  1. 球心:到球面上任意一点距离都相等的点。
  2. 距离:设两个n为空间上的点A, B的坐标为$(a_1, a_2, \cdots , a_n), (b_1, b_2, \cdots , b_n)$,则AB的距离定义为:$dist = \sqrt{ (a_1-b_1)^2 + (a_2-b_2)^2 + \cdots + (a_n-b_n)^2 }$

$1 \le n \le 10$
给出的坐标皆为精确到小数点后$6$位的实数,且绝对值不超过$2000$
输出$n$个实数,表示球心的坐标,精确到小数点后三位
数据保证有解

代码

又要写数学公式了有点兴奋
由题可得:
$$\sum_{j=1}^{n}{(a[i][j] - x[j])^2} = C$$
其中$a[i][j]$是$i$点的$j$维坐标,$x[j]$是球心的$j$维坐标,$C=dist(x,i)^2$,是个常数
将有关$i$和有关$i+1$的方程相减可得
$$\sum_{j=1}{n}{(a[i][j]2 - a[i+1][j]^2 - (a[i][j]-a[i+1][j])\times x[j])} = 0$$
$$\sum_{j=1}^{n}{(a[i][j] -a[i+1][j])\times x[j]}=\sum_{j=1}{n}{(a[i][j]2 - a[i+1][j]^2)}$$
用这样的方式做$n$次相减,我们会得到$n$个$n$元方程
然后?
果断高斯消元求解就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
double twice(double a){ return a*a;}

int main(){
n = read();
for(int i = 1; i <= n + 1; ++ i){
for(int j = 1; j <= n; ++ j){
scanf("%lf", &num[i][j]);
}
}
for(int i = 1; i <= n; ++ i){
for(int j = 1; j <= n; ++ j){
a[i][j] = 2*(num[i+1][j] - num[i][j]);
a[i][n+1] += twice(num[i+1][j]) - twice(num[i][j]);
}
}
for(int i = 1; i <= n; ++ i){
for(int j = i + 1; j <= n; ++ j){
if(a[j][i] > a[i][i]){
for(int k = i; k <= n + 1; ++ k) //注意是 <= n+1
swap(a[j][k], a[i][k]);
}
}
for(int j = 1; j <= n; ++ j){
if(j == i) continue;
double d = a[j][i]/a[i][i];
for(int k = 1; k <= n + 1; ++ k) //同样注意是 <= n+1
a[j][k] -= a[i][k]*d;
}
}
for(int i = 1; i < n; ++ i) printf("%.3f ", a[i][n+1]/a[i][i]);
printf("%.3f", a[n][n+1]/a[n][n]);
//用这种高斯消元求出来的是由n个一元方程组成的对角矩阵
return 0;
}