BZOJ

BZOJ 1013 球形空间产生器

题意

给定n维球上n+1个点的坐标，求球心坐标（保证有解）

数据范围

$$n\leqslant10$$

题解

第一次写高斯消元，历经坎坷终于解决了。
已知球上点坐标(x_1,x_2…x_n)，球心坐标为(a_1,a_2…a_n),那就有：
$$(x_1-a_1)^2+…+(x_n-a_n)^2=x_1^2-2x_1a_1+a_1^2+…+x_n^2-2x_na_n+a_n^2=r^2$$
我们可以写出n+1个这样的式子，将上下两个式子相减得：
$$2(x_1-y_1)a_1+2(x_2-y_2)a_2+…=x_1^2-y_1^2+x_2^2-y_2^2+…$$
左边为n个未知数的一次多项式，右边为常数，进行高斯消元

高斯消元

枚举每一个未知数的n个式子，找到第一个其系数大于0的把它与当前最上面的式子交换，并将其系数化为1（等式两边同时除以原系数）。其余所有等式皆与之相减，消掉当前所枚举的未知数。然后将枚举下一未知数，用下面的等式重复如上步骤。
最后每个等式右边的常数就是该未知数的答案（因为系数是1）。

代码

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
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define eps 1e-6
double f[30],a[30][30],x;
int main()
{
	int n,j,now=1;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lf",&f[i]);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++)
	{
		scanf("%lf",&x);
		a[i][j]=2*(x-f[j]);
		a[i][n+1]+=x*x-f[j]*f[j];
	}
	for (int i=1;i<=n;i++)
	{
		for (j=now;j<=n;j++) if (fabs(a[j][i])>eps) break;
		if (j>n) continue;
		if (j!=now)	for (int k=1;k<=n+1;k++) swap(a[j][k],a[now][k]);
		x=a[now][i];
		for (j=1;j<=n+1;j++) a[now][j]/=x;
		
		for (j=1;j<=n;j++)
		if (j!=now)
		{
			x=a[j][i];
			for (int k=1;k<=n+1;k++) a[j][k]-=x*a[now][k];
		}
		now++;
	}
	for (int i=1;i<n;i++)
	printf("%.3lf ",a[i][n+1]);printf("%.3lf\n",a[n][n+1]);
	return 0;
}