传送门
题目描述
有一个球形空间产生器能够在 nnn 维空间中产生一个坚硬的球体。现在，你被困在了这个 nnn 维球体中，你只知道球面上 n+1n+1n+1 个点的坐标，你需要以最快的速度确定这个 nnn 维球体的球心坐标，以便于摧毁这个球形空间产生器。
输入输出格式
输入格式：
第一行是一个整数 nnn (1<=N=10)(1<=N=10)(1<=N=10) 。接下来的 n+1n+1n+1 行，每行有 nnn 个实数，表示球面上一点的 nnn 维坐标。每一个实数精确到小数点后 666 位，且其绝对值都不超过 200002000020000 。
输出格式：
有且只有一行，依次给出球心的 nnn 维坐标（ nnn 个实数），两个实数之间用一个空格隔开。每个实数精确到小数点后 333 位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。
输入输出样例
输入样例#1：
2
0.0 0.0
-1.0 1.0
1.0 0.0
输出样例#1：
0.500 1.500
说明
提示：给出两个定义：
题解
利用所有点到球心的距离相等 用两个点构造出来方程
例如：若现在是二维
设球心为$（x，y） $有两个点$（a,b）$ $（a‘,b‘）$
点与球心的距离的平方为
$(a-x)^2+(b-y)^2 = a^2-2ax+x^2+b^2-2by+y^2$
减去另一个点得：
$2(a-a‘)x+2(b-b‘)y=a^2-a‘^2+b^2-b‘^2$
列出来高斯消元完事
PS:
1.用一个点与其他所有点进行联系列出方程即可
2.写高斯消元时注意边界
code:
//By Menteur_Hxy#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#define LL long long#define M(a,b) memset(a,(b),sizeof(a))#define F(i,a,b) for(register int i=(a);i<=(b);i++)#define C(i,a,b) for(register int i=(b);i>=(a);i--)using namespace std;LL rd() { ???LL x=0,fla=1; char c=getchar(); ???while(!isdigit(c)) {if(c==‘-‘) fla=-fla;c=getchar();} ???while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=getchar(); ???return x*fla;}const double eps=1e-6;const int N=11;int n;double da[N][N],a[N],ans[N];int gauss() { ???int h=1,l=1; ???for(;h<=n&&l<=n+1;h++,l++) { ???????int r=h; ???????F(i,h+1,n) if(fabs(da[r][l])>fabs(da[i][l])) r=i; ???????if(fabs(da[r][l])<eps) {h--;continue;} ???????if(r!=h) F(i,l,n+1) swap(da[r][i],da[h][i]); ???????F(i,h+1,n) if(fabs(da[i][l])>eps) { ???????????double t=da[i][l]/da[h][l]; ???????????F(j,l,n+1) da[i][j]-=da[h][j]*t; ???????????da[i][l]=0; ???????} ???} ???F(i,h,n) if(fabs(da[i][n+1])>eps) return -1;//无解 ????if(h<n+1) return n+1-h;//自由元个数 ???C(i,1,n) { ???????double tmp=da[i][n+1]; ???????F(j,i+1,n) tmp-=ans[j]*da[i][j]; ???????ans[i]=(tmp/da[i][i]); ???} ???return 0;}int main() { ???n=rd(); ???F(i,1,n) scanf("%lf",&a[i]); ???F(i,1,n) F(j,1,n) { ???????double t; scanf("%lf",&t); ?????????da[i][j]=2*(t-a[j]); ???????da[i][n+1]+=t*t-a[j]*a[j]; ???} ???gauss(); ???F(i,1,n-1) printf("%.3lf ",ans[i]); ???printf("%.3lf\n",ans[n]); ???return 0;}[luogu4035 JSOI2008] 球形空间产生器 （矩阵 高斯消元）
原文地址：https://www.cnblogs.com/Menteur-Hxy/p/9251189.html