【BZOJ1013】球形空间产生器

  考虑二维的情况。

  设球心坐标(x,y),另三个点的坐标为(a1,b1),(a2,b2),(a3,b3)

  可以列出两个方程：

    ①(a1-x)^2+(b1-y)^2=(a2-x)^2+(b2-y)^2

    ②(a1-x)^2+(b1-y)^2=(a3-x)^2+(b3-y)^2

  可以消掉x和y的二次方项，于是可以得到

    ①2(a2-a1)x+2(b2-b1)y=a2^2-a1^2+b2^2-b1^2

    ②2(a3-a1)x+2(b3-b1)y=a3^2-a1^2+b3^2-b1^2

  类似的方法往多维推，然后用高斯消元解方程组。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=14;
const double eps=1e-8;

struct Node
{
	double a[maxn];
	double &operator[] (int x) {return a[x];}
}v[maxn];

double m[maxn][maxn];
int n;

void Gauss()
{
	for (int i=1;i<=n;i++)
	{
		if (fabs(m[i][i])<eps)
			for (int j=i+1;j<=n && fabs(m[i][i])<eps;j++) if (fabs(m[j][i])>eps)
				for (int k=1;k<=n+1;k++) swap(m[i][k],m[j][k]);
		for (int j=n+1;j>=i;j--) m[i][j]/=m[i][i];
		for (int j=1;j<=n;j++) if (j!=i)
		{
			double temp=m[j][i]/m[i][i];
			for (int k=i;k<=n+1;k++) m[j][k]-=temp*m[i][k];
		}
	}
}

int main()
{
	scanf("%d",&n);
	for (int i=0;i<=n;i++) for (int j=1;j<=n;j++) scanf("%lf",&v[i][j]);
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) m[i][j]=2*(v[i][j]-v[0][j]),m[i][n+1]+=v[i][j]*v[i][j]-v[0][j]*v[0][j];
	Gauss();
	for (int i=1;i<n;i++) printf("%.3lf ",m[i][n+1]);printf("%.3lf\n",m[n][n+1]);
	return 0;
}