有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。
有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。
第一行是一个整数，n。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。
有且只有一行，依次给出球心的n维坐标（n个实数），两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。
数据规模：
对于40%的数据，1<=n<=3
对于100%的数据，1<=n<=10
提示：给出两个定义：
1、 球心：到球面上任意一点距离都相等的点。
2、 距离：设两个n为空间上的点A, B的坐标为(a1, a2, …, an), (b1, b2, …, bn)，则AB的距离定义为：dist = sqrt( (a1-b1)^2 + (a2-b2)^2 + … + (an-bn)^2 )
题意：给出n维球的球面上的n+1个点，求出球心
分析：显然，我们会想到用模拟退火，但是题目说要与答案一样才得分，而模拟退火什么的很难保证绝对精确，
所以此题只能用高斯消元
根据提示及球心的定义，设球心为（x1, x2, x3, ...., xn）：
得n+1个式子
(a1-x1)^2+(a2-x2)^2+......+(an-xn)^2 = r^2
(b1-x1)^2+(b2-x2)^2+......+(bn-xn)^2 = r^2
(c1-x1)^2+(c2-x2)^2+......+(cn-xn)^2 = r^2
.........
变形即得n+1个式子
a1^2+a2^2+.....+an^2+ x1^2+x2^2+.....+xn^2 = (2*a1*x1+2*a2*x2+.......+2*an*xn)
b1^2+b2^2+.....+bn^2+ x1^2+x2^2+.....+xn^2 = (2*b1*x1+2*b2*x2+.......+2*bn*xn)
c1^2+c2^2+.....+cn^2+ x1^2+x2^2+.....+xn^2 = (2*c1*x1+2*c2*x2+.......+2*cn*xn)
........
每个式子都与第一个相减，得到n个式子
2*(a1-b1)*x1+2*(a2-b2)*x2+......+2*(an-bn)*xn = (a1^2+a2^2+....+an^2) - (b1^2+b2^2+......+bn^2)
2*(a1-c1)*x1+2*(a2-c2)*x2+......+2*(an-cn)*xn = (a1^2+a2^2+....+an^2) - (c1^2+c2^2+......+cn^2)
..........
其中a1、a2、a3、.......、an，b1、b2、........、bn，.......，都是已知的
所以共有n个式子，n个未知数，用高斯消元即可
综上所述，本题得解
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <iostream> 9 #include <algorithm> 10 #include <map> 11 #include <set> 12 #include <ctime> 13 using namespace std; 14 typedef long long LL; 15 typedef double DB; 16 #define For(i, s, t) for(int i = (s); i <= (t); i++) 17 #define Ford(i, s, t) for(int i = (s); i >= (t); i--) 18 #define MIT (2147483647) 19 #define INF (1000000001) 20 #define MLL (1000000000000000001LL) 21 #define sz(x) ((int) (x).size()) 22 #define clr(x, y) memset(x, y, sizeof(x)) 23 #define puf push_front 24 #define pub push_back 25 #define pof pop_front 26 #define pob pop_back 27 #define ft first 28 #define sd second 29 #define mk make_pair 30 inline void SetIO(string Name) { 31 string Input = Name+".in", 32 Output = Name+".out"; 33 freopen(Input.c_str(), "r", stdin), 34 freopen(Output.c_str(), "w", stdout); 35 } 36 37 const int N = 20; 38 int n; 39 DB Dat[N][N]; 40 DB K[N][N], Ans[N]; 41 42 inline void Input() { 43 scanf("%d", &n); 44 For(i, 0, n) 45 For(j, 1, n) scanf("%lf", &Dat[i][j]); 46 } 47 48 inline DB Sqr(DB x) { 49 return x*x; 50 } 51 52 inline void Solve() { 53 For(i, 1, n) { 54 For(j, 1, n) 55 K[i][j] = 2.0*(Dat[0][j]-Dat[i][j]); 56 K[i][n+1] = 0.0; 57 For(j, 1, n) 58 K[i][n+1] += (Sqr(Dat[0][j])-Sqr(Dat[i][j])); 59 } 60 61 For(i, 1, n) { 62 DB Max = -1.0*MLL; 63 int x; 64 For(j, i, n) 65 if(Max < K[j][i]) { 66 Max = K[j][i]; 67 x = j; 68 } 69 For(j, i, n+1) swap(K[i][j], K[x][j]); 70 For(j, i+1, n) { 71 DB Temp = K[j][i]/K[i][i]; 72 For(w, i, n+1) K[j][w] -= Temp*K[i][w]; 73 } 74 } 75 76 Ford(i, n, 1) { 77 Ford(j, n, i+1) K[i][n+1] -= K[i][j]*Ans[j]; 78 Ans[i] = K[i][n+1]/K[i][i]; 79 } 80 81 For(i, 1, n-1) printf("%.3lf ", Ans[i]); 82 printf("%.3lf\n", Ans[n]); 83 } 84 85 int main() { 86 SetIO("1013"); 87 Input(); 88 Solve(); 89 return 0; 90 }
原文：http://www.cnblogs.com/StupidBoy/p/4595497.html
