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

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

2

0.0 0.0

-1.0 1.0

1.0 0.0

输出样例#1：

0.500 1.500

说明

提示：给出两个定义：

[luogu4035 JSOI2008] 球形空间产生器（矩阵高斯消元）-LMLPHP

题解

利用所有点到球心的距离相等用两个点构造出来方程

例如：若现在是二维

设球心为$（x，y） $有两个点$（a,b）$ $（a',b'）$

点与球心的距离的平方为

$(a-x)^2+(b-y)^2 = a^2-2ax+x^2+b^2-2by+y^2$

减去另一个点得：

$2(a-a')x+2(b-b')y=a^2-a'^2+b^2-b'^2$

列出来高斯消元完事

PS:

1.用一个点与其他所有点进行联系列出方程即可

2.写高斯消元时注意边界

code:

//By Menteur_Hxy

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#define LL long long

#define M(a,b) memset(a,(b),sizeof(a))

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

#define C(i,a,b) for(register int i=(b);i>=(a);i--)

using namespace std;

LL rd() {

    LL x=0,fla=1; char c=getchar();

    while(!isdigit(c)) {if(c=='-') fla=-fla;c=getchar();}

    while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x*fla;

}

const double eps=1e-6;

const int N=11;

int n;

double da[N][N],a[N],ans[N];

int gauss() {

    int h=1,l=1;

    for(;h<=n&&l<=n+1;h++,l++) {

        int r=h;

        F(i,h+1,n) if(fabs(da[r][l])>fabs(da[i][l])) r=i;

        if(fabs(da[r][l])<eps) {h--;continue;}

        if(r!=h) F(i,l,n+1) swap(da[r][i],da[h][i]);

        F(i,h+1,n) if(fabs(da[i][l])>eps) {

            double t=da[i][l]/da[h][l];

            F(j,l,n+1) da[i][j]-=da[h][j]*t;

            da[i][l]=0;

        }

    }

    F(i,h,n) if(fabs(da[i][n+1])>eps) return -1;//无解

    if(h<n+1) return n+1-h;//自由元个数

    C(i,1,n) {

        double tmp=da[i][n+1];

        F(j,i+1,n) tmp-=ans[j]*da[i][j];

        ans[i]=(tmp/da[i][i]);

    }

    return 0;

}

int main() {

    n=rd();

    F(i,1,n) scanf("%lf",&a[i]);

    F(i,1,n) F(j,1,n) {

        double t; scanf("%lf",&t);

        da[i][j]=2*(t-a[j]);

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

    }

    gauss();

    F(i,1,n-1) printf("%.3lf ",ans[i]);

    printf("%.3lf\n",ans[n]);

    return 0;

}

1N