一般来说,对于n个一次方程和n个未知数,可以通过高斯消元法来判断这个方程无解,有唯一解还是有多解。对于一个有唯一解的方程,我们可以通过程序实现加减消元和代入消元,以此来求得这个方程的解。
先贴一个解普通方程的模板:
void Gauss(int m, int n) { int i = 0, j = 0; for (; i < m && j < n; i++, j++) { int mx = i; for (int k = i + 1; k < m; k++) if (fabs(a[k][j]) > fabs(a[mx][j])) mx = k; if (fabs(a[mx][i]) < eps) {i--; continue;} if (mx ^ i) swap(a[mx], a[i]); for (int k = 1; k < m; k++) if (k ^ i) { double tmp = a[j][i] / a[i][i]; for (int l = j; l <= n; l++) a[k][l] -= tmp * a[k][l]; } } }
1. [JSOI2008 Round1] 球形空间产生器
问题描述
火星人不能忍受地球人对他们的歧视,终于发明了一种非常强大的武器:球形空间产生器。球形空间产生器能产生一个N维球体屏障,而且这个屏障是坚不可摧的,被困在球体内的地球人就被切断了与外界的联系。Js08现在就被困在了屏障中,情况十分危急,必须尽快找出并摧毁球形空间产生器。Js08经过摸索和碰壁,给出了球体上N+1个点的坐标,希望你能够帮Js08找出球形空间产生器的位置——它总是位于球形空间的球心。
输入格式
第一行为整数N,代表了空间的维度。
接下来N+1行,每行N个实数代表一个坐标。输入数据精确到小数点后6位。
输入数据保证输出结果唯一。
输出格式
输出一行N个实数,代表球心的坐标,精确到小数点后三位。相邻的数字之间用一个空格分开(行末无空格)。
数据规模:对于40%的数据,1<=n<=3
对于100%的数据,1<=n<=10 思路:这个题其实就是一个高斯消元的板题。为什么呢?我们来看题。 首先,假设这个球心为 (X1, X2, X3, X4, ... , Xn) ,第i个球的坐标为(Xi1, Xi2, Xi3, Xi4, ... , Xin)