题目链接： P4035 [JSOI2008]球形空间产生器
题目大意： 在 n ( n ≤ 10 ) n(n\leq10) n(n≤10)维空间中，给出一个 n n n维球体上的 n + 1 n+1 n+1个点，求这个球的球心坐标。
题目分析： 考虑将第 n n n维中，将第 i i i个点的第 j j j维表示为 x i j x_{ij} xij，设球心的坐标为 x 0 k x_{0k} x0k则对于这 n n n个点构成的方程组为 { ( x 11 − x 01 ) 2 + ( x 12 − x 02 ) 2 + . . . + ( x 1 n − x 0 n ) 2 = r 2 ( x 21 − x 01 ) 2 + ( x 22 − x 02 ) 2 + . . . + ( x 2 n − x 0 n ) 2 = r 2 . . . . . ( x n 1 − x 01 ) 2 + ( x n 2 − x 02 ) 2 + . . . + ( x n n − x 0 n ) 2 = r 2 \left\{ \begin{array}{l} (x_{11}-x_{01})^2+(x_{12}-x_{02})^2+...+(x_{1n}-x_{0n})^2=r^2\\ (x_{21}-x_{01})^2+(x_{22}-x_{02})^2+...+(x_{2n}-x_{0n})^2=r^2\\ ..... \\ (x_{n1}-x_{01})^2+(x_{n2}-x_{02})^2+...+(x_{nn}-x_{0n})^2=r^2\\ \end{array} \right. ⎩⎪⎪⎨⎪⎪⎧(x11−x01)2+(x12−x02)2+...+(x1n−x0n)2=r2(x21−x01)2+(x22−x02)2+...+(x2n−x0n)2=r2.....(xn1−x01)2+(xn2−x02)2+...+(xnn−x0n)2=r2 把括号拆开 { x 11 2 − 2 x 11 x 01 + x 01 2 + . . . + x 1 n 2 − 2 x 1 n x 0 n + x 0 n 2 = r 2 x 21 2 − 2 x 21 x 01 + x 01 2 + . . . + x 2 n 2 − 2 x 2 n x 0 n + x 0 n 2 = r 2 . . . . . . x n 1 2 − 2 x n 1 x 01 + x 01 2 + . . . + x n n 2 − 2 x n n x 0 n + x 0 n 2 = r 2 \left\{ \begin{array}{l} x_{11}^2-2x_{11}x_{01}+x_{01}^2+...+x_{1n}^2-2x_{1n}x_{0n}+x_{0n}^2=r^2\\ x_{21}^2-2x_{21}x_{01}+x_{01}^2+...+x_{2n}^2-2x_{2n}x_{0n}+x_{0n}^2=r^2\\ ......\\ x_{n1}^2-2x_{n1}x_{01}+x_{01}^2+...+x_{nn}^2-2x_{nn}x_{0n}+x_{0n}^2=r^2\\ \end{array} \right. ⎩⎪⎪⎨⎪⎪⎧x112−2x11x01+x012+...+x1n2−2x1nx0n+x0n2=r2x212−2x21x01+x012+...+x2n2−2x2nx0n+x0n2=r2......xn12−2xn1x01+x012+...+xnn2−2xnnx0n+x0n2=r2 将相邻的式子作差 ( ① − ② , ② − ③ . . . ) (①-②,②-③...) (①−②,②−③...)得到 n n n个方程 { 2 ( x 21 − x 11 ) x 01 + . . . + 2 ( x 2 n − x 1 n ) x 0 n = x 11 2 − x 21 2 + . . . + x 1 n 2 − x 2 n 2 2 ( x 31 − x 21 ) x 01 + . . . + 2 ( x 3 n − x 2 n ) x 0 n = x 21 2 − x 31 2 + . . . + x 2 n 2 − x 3 n 2 . . . 2 ( x n 1 − x ( n − 1 ) 1 ) x 01 + . . . + 2 ( x n n − x ( n − 1 ) n ) x 0 n = x ( n − 1 ) 1 2 − x n 1 2 + . . . + x ( n − 1 ) n 2 − x n n 2 \left\{ \begin{array}{l} 2(x_{21}-x_{11})x_{01}+...+2(x_{2n}-x_{1n})x_{0n}=x_{11}^2-x_{21}^2+...+x_{1n}^2-x_{2n}^2\\ 2(x_{31}-x_{21})x_{01}+...+2(x_{3n}-x_{2n})x_{0n}=x_{21}^2-x_{31}^2+...+x_{2n}^2-x_{3n}^2\\ ...\\ 2(x_{n1}-x_{(n-1)1})x_{01}+...+2(x_{nn}-x_{(n-1)n})x_{0n}=x_{(n-1)1}^2-x_{n1}^2+...+x_{(n-1)n}^2-x_{nn}^2\\ \end{array} \right. ⎩⎪⎪⎨⎪⎪⎧2(x21−x11)x01+...+2(x2n−x1n)x0n=x112−x212+...+x1n2−x2n22(x31−x21)x01+...+2(x3n−x2n)x0n=x212−x312+...+x2n2−x3n2...2(xn1−x(n−1)1)x01+...+2(xnn−x(n−1)n)x0n=x(n−1)12−xn12+...+x(n−1)n2−xnn2 到这里，题目就变成了一个高斯消元的裸题，代码如下： 题目代码：
#include<stdio.h> #include<algorithm> #include<string.h> #define swap(a,b)(a+=b,b=a-b,a=a-b) using namespace std; double x[100][100],m[100][100]; int n,flag; void Gauss(){ for(int i=1;i<=n;i++){ if(!m[i][i]){ flag=1; for(int j=i;j<=n;j++)if(m[j][i]){ flag=0; for(int k=1;k<=n+1;k++) swap(m[i][k],m[j][k]); break; } } for(int j=1;j<=n;j++)if(i^j){ double ns=m[j][i]/m[i][i]; for(int k=1;k<=n+1;k++) m[j][k]-=m[i][k]*ns; } } for(int i=1;i<=n;i++) m[i][n+1]/=m[i][i]; for(int i=1;i<=n;i++) printf("%.3f ",m[i][n+1]); } int main() { scanf("%d",&n); for(int i=1;i<=n+1;i++) for(int j=1;j<=n;j++) scanf("%lf",&x[i][j]); for(int i=2;i<=n+1;i++) for(int j=1;j<=n;j++){ m[i-1][j]=2*(x[i][j]-x[i-1][j]); m[i-1][n+1]+=(x[i][j]*x[i][j])-(x[i-1][j]*x[i-1][j]); } Gauss(); return 0; }