Luogu4035[JSOI2008]球形空间产生器

Luogu4035[JSOI2008]球形空间产生器

题面：洛谷

解析

根据题目所给公式化简消去二次项，高斯消元即可。

代码

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#define N 15
using namespace std;
int n; double p[N][N],a[N][N],x[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n+1;++i)
    for(int j=1;j<=n;++j)
    scanf("%lf",&p[i][j]);
    for(int i=1;i<=n;++i){
        double sum=0;
        for(int j=1;j<=n;++j){
            a[i][j]=-2.0*p[i][j]+2.0*p[i+1][j];
            sum+=p[i][j]*p[i][j]-p[i+1][j]*p[i+1][j];
        }
        a[i][n+1]=-sum;
    }
    for(int i=1,q;i<n;++i){
        q=0;
        for(int j=i;j<=n;++j) if(!q||a[j][i]>a[q][i]) q=j;
        swap(a[i],a[q]);
        for(int j=i+1;j<=n;++j) for(int k=n+1;k>=i;--k)
        a[j][k]-=a[i][k]*a[j][i]/a[i][i];
    }
    for(int i=n;i;--i){
        x[i]=a[i][n+1];
        for(int j=n;j>i;--j) x[i]-=x[j]*a[i][j];
        x[i]/=a[i][i];
    }
    for(int i=1;i<=n;++i) printf("%.3lf%c",x[i],(i==n)?'
':' ');
    return 0;
}