P4035 [JSOI2008] 球形空间产生器

p4035,jsoi2008 · 浏览次数 : 0

小编点评

这段代码实现了一个用于解决高斯消元法的程序，主要用于求解n维空间中n+1个点与球心距离相等的n维坐标问题。首先，程序读取输入的n值，然后初始化两个数组a和b，分别表示n+1个点和球心的坐标。接下来，通过两层循环，计算出每个点的球心坐标（即n维空间中点到球心的距离为r的点）。然后，程序使用差分消元法（Gaussian elimination）求解n个一元一次方程组，以得到n维坐标的解。具体来说，将第二个循环中的每个元素减去第一个元素，得到n-1个新的方程，然后用这些新方程替换原方程组中的对应方程，重复此过程直到只剩下一个方程。这样，就可以得到n个未知数的解。最后，程序输出结果，即每个坐标的解。以下是该程序的输入输出示例： ``` 5 1.0 2.0 3.0 4.0 5.0 1.0 1.0 1.0 1.0 1.0 1.0 2.0 3.0 4.0 5.0 1.0 1.0 1.0 1.0 1.0 1.0 2.0 3.0 4.0 5.0 ``` 输出结果为： ``` 0.000 2.785 0.500 1.500 1.000 0.000 1.500 -1.000 2.000 -2.785 ```

正文

高斯消元例题

题目要求的是球心的 n 维坐标，给了n+1个点的坐标，用二维的圆来思考,n+1个点到圆心的距离相等，可以列出n+1个等式

√∑(a_i,j-bj)²=r(r为半径)

两边同时平方得到∑(a_i,j-b_j)²=r²

因为a_i,j已知，所以有n+1个二次方程来解n维坐标和r。

考虑学过的算法并没有高效解多个二次方程的方法，只有高斯消元解线性方程组，所以要去掉二次项。

因为有n+1个方程但真正要求的只有n个数，考虑做差消去二次项。

第i+1去减i可以得到∑2b_j*(a_i,j-a_i+1,j)=∑a_i,j²-a_i+1,j²

n个一元一次方程，n个未知数，高斯消元求解即可。

#include <bits/stdc++.h>
using namespace std;
double a[20][20],b[20][20];
int n;
void ycl()
{
    for(int i=1;i<=n+1;i++)
    {
        double ans=0;
        for(int j=1;j<=n;j++)
            scanf("%lf",&a[i][j]),ans+=a[i][j]*a[i][j];    
        a[i][n+1]=ans;    
    }        
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            b[i][j]=2*(a[i][j]-a[i+1][j]);
        b[i][n+1]=a[i+1][n+1]-a[i][n+1];
    }    
} 
int main()
{
    scanf("%d",&n);
    ycl();
    for(int i=1;i<=n;i++)
    {
        int mx=i;
        for(int j=i+1;j<=n;j++)
        {
            if(fabs(b[j][i])>fabs(b[mx][i]))mx=j;
        }
        swap(b[i],b[mx]);
        for(int j=1;j<=n;j++)
        {
            if(j==i)continue;
            double div=b[j][i]/b[i][i];
            for(int k=i;k<=n+1;k++)b[j][k]-=b[i][k]*div;
        }
    } 
    for(int i=1;i<=n;i++)
    {
        printf("%.3lf ",-1*b[i][n+1]/b[i][i]); 
    }
    return 0;
}

与P4035 [JSOI2008] 球形空间产生器相似的内容：

P4035 [JSOI2008] 球形空间产生器

高斯消元例题题目要求的是球心的 n 维坐标，给了n+1个点的坐标，用二维的圆来思考,n+1个点到圆心的距离相等，可以列出n+1个等式 √∑(ai,j-bj)2=r(r为半径) 两边同时平方得到∑(ai,j-bj)2=r2 因为ai,j已知，所以有n+1个二次方程来解n维坐标和r。考虑学过的算法并