[BZOJ1013/Luogu4035][JSOI2008]球形空间产生器sphere(高斯消元)

发布于 2018-01-20  109 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1013/Luogu4035][JSOI2008]球形空间产生器sphere(高斯消元)

Description

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

Http

BZOJ
Luogu

Tag

高斯消元

题目大意

求解方程组

解决思路

根据题目给出的计算\(n\)维空间的两点坐标公式,我们可以列出\(n+1\)个连等式,随便选择一个作为基准,其它的都与它相消,便可以去掉所有的未知数的平方项,然后高斯消元即可

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ld long double

const int maxN=20;
const int inf=2147483647;

int n;
ld Mat[maxN][maxN];
ld Input[maxN][maxN];
ld Ans[maxN];

void Guess();

int main()
{
    scanf("%d",&n);//读入数据
    for (int i=0;i<=n;i++) for (int j=1;j<=n;j++) scanf("%LF",&Input[i][j]);
    for (int i=1;i<=n;i++)//构造n个方程
    {
        for (int j=1;j<=n;j++) Mat[i][j]=(ld)2*(Input[i][j]-Input[0][j]);
        ld s1=0,s2=0;
        for (int j=1;j<=n;j++) s1=s1+Input[i][j]*Input[i][j],s2=s2+Input[0][j]*Input[0][j];
        Mat[i][n+1]=s1-s2;
    }
    Guess();//高斯消元
    printf("%.3LF",Ans[1]);
    for (int i=2;i<=n;i++) printf(" %.3LF",Ans[i]);
    return 0;
}

void Guess()//从上到下消元
{
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
        {
            ld ret=Mat[j][i]/Mat[i][i];
            for (int k=i;k<=n+1;k++)
                Mat[j][k]-=Mat[i][k]*ret;
        }
    Ans[n]=Mat[n][n+1]/Mat[n][n];
    for (int i=n-1;i>=1;i--)//从下到上得到答案
    {
        ld sum=0;
        for (int j=i;j<=n;j++) sum=sum+Mat[i][j]*Ans[j];
        Ans[i]=(Mat[i][n+1]-sum)/Mat[i][i];
    }
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1013/Luogu4035][JSOI2008]球形空间产生器sphere(高斯消元)


HNCJ OIer