[JSOI2008]球形空间产生器 （高斯消元）

时间：2023-03-08 21:08:49

[JSOI2008]球形空间产生器

[JSOI2008]球形空间产生器 （高斯消元）

$ solution: $

非常明显的一道高斯消元。给了你n+1个球上的位置，我们知道球上任何一点到球心的距离是相等，所以我们

可以利用这一个性质。我们用n+1个球上的位置，两两组成n个等式（以距离为桥梁），将等式左右两边消元

即可得到n组多元方程，然后高斯消元即可！

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

const db cha=1e-9;

int n;

db a[13][13];

db g[13][13];

inline int qr(){

    char ch;

    while((ch=getchar())<'0'||ch>'9');

    int res=ch^48;

    while((ch=getchar())>='0'&&ch<='9')

        res=res*10+(ch^48);

    return res;

}

inline void swap(db &x,db &y){db z=x;x=y;y=z;}

inline db fabs(db x){return x<0?-x:x;}

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    n=qr();

    for(rg i=1;i<=n+1;++i)

        for(rg j=1;j<=n;++j)

            scanf("%lf",&a[i][j]);

    for(rg i=1;i<=n;++i){

        for(rg j=1;j<=n;++j){

            g[i][j]=(a[i+1][j]-a[i][j])*2;

            g[i][n+1]+=a[i+1][j]*a[i+1][j]-a[i][j]*a[i][j];

        }

    }

    for(rg i=1;i<=n;++i){

        rg f=i;

        for(rg j=i+1;j<=n;++j)

            if(fabs(g[j][i])>fabs(g[f][i]))f=j;

        if(f!=i)swap(g[i],g[f]);

        for(rg j=1;j<=n;++j){

            if(i==j)continue;

            db tmp=g[j][i]/g[i][i];

            for(rg k=i;k<=n+1;++k)

                g[j][k]-=g[i][k]*tmp;

        }

    }

    for(rg i=1;i<=n;++i)

        printf("%.3lf ",g[i][n+1]/g[i][i]);

    return 0;

}

相关文章