球形空间产生器

题面

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

数据范围:

$1<=N<=10$

思路

首先球心到达每个点的距离是相等的,我们可以依据这个来列方程,然后用高斯消元求解。

数学

以二维为例:

设中心坐标为$(x_0,y_0)$半径为$r$,则可以列出方程:

$(x_1 - x_0)^2 + (y_1 - y_0)^2 = r^2$ ①

$(x_2 - x_0)^2 + (y_2 - y_0)^2 = r^2$ ②

①$-$②得:

$(x_1 - x_0)^2 + (y_1 - y_0)^2 - (x_2 - x_0)^2 - (y_2 - y_0)^2 = 0$

化简得:

$(x_1 + x_2 - 2x_0)(x_1 - x_2) + (y_1 + y_2 - 2y_0)(y_1 - y_2) = 0$

$x_1^2 - x_2^2 + y_1^2 - y_2^2 - 2(x_1 - x_2)x_0 - 2(y_1 - y_2)y_0 = 0$

其中$x_1,x_2,y_1,y_2$是已知的。我们可以将后两项移项,得到高斯消元的基本式。

然后我们就可以愉快地上模板了。

[代码]
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
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
const int maxn = 15;
const int eps = 1e-8;
int n;
double a[maxn][maxn],Matrix[maxn][maxn],del;
bool guass()
{
for(int i = 1 ; i <= n ; ++ i)
{
int k = i;
for(int j = i + 1 ; j <= n ; ++ j)if(fabs(Matrix[j][i] > fabs(Matrix[k][i])))k = j;
if(fabs(del = Matrix[k][i]) < eps)return 0;
//swap(Matrix[i], Matrix[k]);
for(int j = i ; j <= n + 1 ; ++ j)swap(Matrix[i][j],Matrix[k][j]);
for(int j = i ; j <= n + 1 ; ++ j)Matrix[i][j] /= del;
for(int k = 1 ; k <= n ; ++ k)
if(k != i){
del = Matrix[k][i];
for(int j = i ; j <= n + 1 ; ++ j)Matrix[k][j] -= del * Matrix[i][j];
}
}
return 1;
}
int main()
{
// ios::sync_with_stdio(0);
cin >> n;
for(int i = 1 ; i <= n + 1 ; ++ i)
for(int j = 1 ; j <= n ; ++ j)
cin >> a[i][j];
for(int i = 1 ; i <= n ; ++ i)
{
for(int k = 1 ; k <= n ; ++ k)
{
Matrix[i][k] = 2 * (a[i][k] - a[i + 1][k]);
Matrix[i][n + 1] += (a[i][k] * a[i][k] - a[i + 1][k] * a[i + 1][k]);
}
// Matrix[i][n + 1] = res;
}
guass();
for(int i = 1 ; i <= n ; ++ i)
printf("%.3lf ",Matrix[i][n + 1]);
return 0;
}