[BZOJ1013][JSOI2008]球形空间产生器sphere

题面戳我
给你n+1个n维坐标，求它们的球心坐标。保证数据有解。n<=10
n维上的距离定义：设两个n维空间上的点(A),(B)的坐标为((a_1, a_2, …, a_n)), ((b_1, b_2, …, b_n))，则AB的距离定义为：

[dist = sqrt {(a_1-b_1)^2 + (a_2-b_2)^2 +… + (a_n-b_n)^2} ]

sol

首先n+1个点确定一个n维的球没错吧（三点确定一个圆嘛）
而n维空间的坐标相当于一个n维向量，有n个未知变量
所以就想到列方程啊，列出n个方程就可以了
我们设球心坐标((x_0,y_0,z_0...))，那么每个点到球心的距离都相等，通过这个两两列等式（其实只要用第一个坐标和后面的n个坐标列等式就可以了）
比如说这样（为避免精度问题所以不开方）

[(x-x_0)^2+(y-y_0)^2+(z-z_0)^2+...=(x'-x_0)^2+(y'-y_0)^2+(z'-z_0)^2+... ]

拆了

[2(x'-x)x_0+2(y'-y)y_0+2(z'-z)z_0=x'^2+y'^2+z'^2+...-x^2-y^2-z^2-... ]

整体看来这就是n个n元方程嘛
所以高斯消元即可

code

注意输出处理，不然会PE。。。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 20;
int n;
double x[N][N],a[N][N],tot[N],sol[N];
int main()
{
	scanf("%d",&n);
	for (int i=0;i<=n;i++)
		for (int j=1;j<=n;j++)
			scanf("%lf",&x[i][j]),tot[i]+=x[i][j]*x[i][j];
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
			a[i][j]=2*(x[i][j]-x[0][j]);
		a[i][n+1]=tot[i]-tot[0];
	}
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++)
			for (int k=n+1;k>=i;k--)
				a[j][k]-=a[i][k]*a[j][i]/a[i][i];
	for (int i=n;i;i--)
	{
		sol[i]=a[i][n+1];
		for (int j=n;j>i;j--) sol[i]-=a[i][j]*sol[j];
		sol[i]/=a[i][i];
	}
	for (int i=1;i<=n;i++)
		if (i<n) printf("%.3lf ",sol[i]);
		else printf("%.3lf",sol[i]);
	return 0;
}