BZOJ 1013 [JSOI2008]球形空间产生器sphere 高斯消元

Description#

　有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在，你被困在了这个n维球体中，你只知道球面上n+1个点的坐标，你需要以最快的速度确定这个n维球体的球心坐标，以便于摧毁这个球形空间产生器。

Input#

　第一行是一个整数n(1<=N=10)。接下来的n+1行，每行有n个实数，表示球面上一点的n维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。

Output#

　有且只有一行，依次给出球心的n维坐标（n个实数），两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。你的答案必须和标准输出一模一样才能够得分。

Sample Input#

2
0.0 0.0
-1.0 1.0
1.0 0.0

Sample Output#

0.500 1.500

题解#

直接列方程到每个点距离相等
手动化简一下就出来了

BZOJ 竟然不能多输出一个空格（气）

1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
#include<cmath>
5
using namespace std;
6
double c[20],a[15][15],b[15],x[15],d;
7
int n;
8
void gauss(){
9
    int im,num=1;
10
    for(int k=1;k<=n;k++,num++){
11
        im=k;
12
        for(int i=k+1;i<=n;i++)
13
            if(fabs(a[i][k])>fabs(a[im][k]))
14
                im=i;
15
        if(im!=k){
16
            for(int i=k;i<=n;i++)
17
                swap(a[num][i],a[im][i]);
18
            swap(b[num],b[im]);
19
        }
20
        if(!a[num][k]){num--;continue;}
21
        for(int i=num+1;i<=n;i++){
22
            if(!a[num][k])continue;
23
            double t=a[i][k]/a[num][k];
24
            for(int j=k;j<=n+1;j++){
25
                a[i][j]-=t*a[k][j];
26
            }
27
            b[i]-=t*b[k];
28
        }
29
    }
30
    for(int i=n;i>=1;i--){
31
        for(int j=n;j>=i+1;j--)
32
            b[i]-=a[i][j]*x[j];
33
        x[i]=b[i]/a[i][i];
34
    }
35
}
36
int main()
37
{
38
    scanf("%d",&n);
39
    for(int i=1;i<=n;i++)scanf("%lf",&c[i]);
40
    for(int i=1;i<=n;i++){
41
        for(int j=1;j<=n;j++){
42
            scanf("%lf",&d);
43
            a[i][j]=d-c[j];
44
            b[i]+=d*d-c[j]*c[j];
45
        }
46
        b[i]/=2;
47
    }
48
    gauss();
49
    for(int i=1;i<n;i++){
50
        printf("%.3lf ",x[i]);
51
    }
52
    printf("%.3lf",x[n]);
53
}