JSOI2008 球形空间产生器

题目:

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

思路:

  利用球形的解析式(拓展到n维)可以用这n+1个点列n个以球心的n个维为未知数的方程。。。再利用高斯消元求解就行了。。。。

代码:

#include <bits/stdc++.h>
#define MAXN 30
#define pow(a) ((a)*(a))
using namespace std;
typedef double Matrix[MAXN][MAXN];
void gauss(Matrix m,int n){
    double *a[MAXN];
    for(int i=0;i<n;i++)
        a[i]=m[i];
    for(int i=0;i<n;i++){
        int r=i;
        for(int j=i+1;j<n;j++)
            if(fabs(a[j][i])>fabs(a[r][i]))
                r=j;
        swap(a[r],a[i]);
        for(int k=i+1;k<n;k++){
            double f=a[k][i]/a[i][i];
            for(int j=i;j<=n;j++)
                a[k][j]-=f*a[i][j];
        }
    }
    for(int i=n-1;~i;i--){
        for(int j=i+1;j<n;j++)
            a[i][n]-=a[j][n]*a[i][j];
        a[i][n]/=a[i][i];
    }
    for(int i=0;i<n;i++){
        if(i)
            putchar(' ');
        printf("%.3lf",a[i][n]); 
    }
}
int main(){
    Matrix a;
    double p[MAXN][MAXN];
    int n;
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
        for(int j=0;j<n;j++)
            scanf("%lf",&p[i][j]);
    for(int i=0;i<n;i++){
        int k=i+1;
        for(int j=0;j<n;j++)
            a[i][j]=2*(p[i][j]-p[k][j]);
        a[i][n]=0;
        for(int j=0;j<n;j++)
            a[i][n]+=pow(p[i][j])-pow(p[k][j]);
    }
    gauss(a,n);
    return 0;
}