欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-18 16:35:04
...

题目:

我是超链接

题解:

根据题目给出的信息,我们列柿子

(a1x)2+(b1y)2=r2
(a2x)2+(b2y)2=r2
(a3x)2+(b3y)2=r2

然后展开

a12+x2+b12+y2=r2+2a1x+2b1y

a22+x2+b22+y2=r2+2a2x+2b2y

a32+x2+b32+y2=r2+2a3x+2b3y

这个平方我们不能用什么算法计算,就让所有的式子都减去第一个式子消去未知数平方吧

2(a2a1)x+2(b2b1)y=a22a12+b22b12

这样只有两个式子两个未知数啦,我们可以解方程了,是高斯消元的板子题了
高斯消元的讲解
不难发现,高斯消元的效率是O(n3)

代码:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps=1e-9;
double ans[15],a[15][15],b[15],x[15];int n;
void gauss()
{
    for (int i=1;i<=n;i++)
    {
        int num=i;
        for (int j=i+1;j<=n;j++)
          if (fabs(a[j][i])>fabs(a[num][i])) num=j;
        for (int j=i;j<=n;j++) swap(a[num][j],a[i][j]);
        swap(b[num],b[i]);
        for (int j=i+1;j<=n;j++)
        {
            if (fabs(a[j][i])<=eps) continue;
            double t=a[j][i]/a[i][i];
            for (int k=i;k<=n;k++) a[j][k]-=t*a[i][k];
            b[j]-=t*b[i];
        }
    }
    for (int i=n;i>=1;i--)
    {
        ans[i]=b[i]/a[i][i];
        for (int j=1;j<i;j++) b[j]-=ans[i]*a[j][i]; 
    }
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lf",&x[i]);
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
      {
        double xx;scanf("%lf",&xx);
        a[i][j]=2*(xx-x[j]);
        b[i]+=xx*xx-x[j]*x[j];
      }
    gauss();
    for (int i=1;i<n;i++) printf("%.3lf ",ans[i]);
    printf("%.3lf",ans[n]);
}

普及向

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

相关标签: 高斯消元