[bzoj1013]：[JSOI2008]球形空间产生器sphere

本文主要是介绍[bzoj1013]：[JSOI2008]球形空间产生器sphere，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
这个题提示太给力了。。。

提示：给出两个定义：1、球心：到球面上任意一点距离都相等的点。2、距离：设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn)，则AB的距离定义为：dist = sqrt( (a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2 )

从这个题的提示中，我们已经可以看出来这个题的算法了。。。
高斯消元，很明显，我们只要用提示中的那个距离公式，列出n+1个方程，然后解就好了
现在的问题是，列出来的方程是二次方程，怎么解呢？
我们注意到，其实只有n个要求的未知数，然而我们有n+1个方程
所以，有一个方程一定不是消元用的
那么那个方程是干什么的呢？
辅助。
我们只要将其他所有方程都减去第一个方程
我们就可以得到n个一次方程
这样，问题就解决了。
代码好短（我不愧为压行选手）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
int n;
double pos[12][12];
double a[12][12];
inline void gauss(){for(int i=1;i<=n;i++){int mx=i;for(int j=i+1;j<=n;j++)if(a[j][i]>a[mx][i])mx=j;for(int j=i;j<=n+1;j++)swap(a[i][j],a[mx][j]);for(int j=i+1;j<=n+1;j++)a[i][j]/=a[i][i];a[i][i]=1.0;for(int j=1;j<=n;j++){if(j==i)continue;for(int k=i+1;k<=n+1;k++){a[j][k]-=a[j][i]*a[i][k];}a[j][i]=0;}}
}
int main(){n=read();for(int i=0;i<=n;i++)for(int j=1;j<=n;j++)scanf("%lf",&pos[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=2.0*(pos[i][j]-pos[0][j]),a[i][n+1]-=pos[0][j]*pos[0][j]-pos[i][j]*pos[i][j];gauss();for(int i=1;i<n;i++)printf("%.3lf ",a[i][n+1]);printf("%.3lf",a[n][n+1]);return 0;
}