[BZOJ1013][JSOI2008]球形空间产生器sphere(高斯消元)
程序员文章站
2024-03-18 16:35:04
...
题目:
题解:
根据题目给出的信息,我们列柿子
然后展开
这个平方我们不能用什么算法计算,就让所有的式子都减去第一个式子消去未知数平方吧
这样只有两个式子两个未知数啦,我们可以解方程了,是高斯消元的板子题了
高斯消元的讲解
不难发现,高斯消元的效率是的
代码:
#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]);
}