M_sea

洛谷4035 [JSOI2008]球形空间产生器
Luogu算法题目给出了$n+1$个$n$维点的坐标$(a_{i,1},a_{i,2},...,a_{i,n})$...
扫描右侧二维码阅读全文
10
2018/08

洛谷4035 [JSOI2008]球形空间产生器

Luogu

算法

题目给出了$n+1$个$n$维点的坐标$(a_{i,1},a_{i,2},...,a_{i,n})$。

我们要求出一个$n$维点,使得$\sum\limits_{j=0}^{n}(a_{i,j}-x_j)^2=C$。(C为常数,$i\in[1,n+1]$)。

这个方程由$n+1$个$n$元二次方程构成,所以将相邻的两个方程作差,消去二次项,得到:

$$\sum\limits_{j=1}^{n}({a_{i,j}}^2-{a_{i+1,j}}^2-2x_j(a_{i,j}-a_{i+1,j}))=0$$

移项得到:

$$\sum\limits_{j=1}^{n}2(a_{i,j}-a_{i+1,j})x_j=\sum_{j=1}^{n}({a_{i,j}}^2-{a_{i+1,j}}^2)$$

右边已知,左边各项系数已知。

用高斯消元法解线性方程组即可。

此题不用判无解。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

const double EPS=1e-8;

double a[20][20],b[20],c[20][20];

int main() {
    ios::sync_with_stdio(false);
    int n; cin>>n;
    for (re int i=1;i<=n+1;i++)
        for (re int j=1;j<=n;j++)
            cin>>a[i][j];
    for (re int i=1;i<=n;i++)
        for (re int j=1;j<=n;j++) {
            c[i][j]=2*(a[i][j]-a[i+1][j]);
            b[i]+=(a[i][j]*a[i][j]-a[i+1][j]*a[i+1][j]);
        }
    for (re int i=1;i<=n;i++) {
        for (re int j=i;j<=n;j++) {
            if (fabs(c[j][i])>EPS) {
                for (re int k=1;k<=n;k++) swap(c[i][k],c[j][k]);
                swap(b[i],b[j]);
            }
        }
        for (re int j=1;j<=n;j++) {
            if (i==j) continue;
            double rate=c[j][i]/c[i][i];
            for (re int k=i;k<=n;k++) c[j][k]-=c[i][k]*rate;
            b[j]-=b[i]*rate;
        }
    }
    for (re int i=1;i<=n;i++) printf("%.3f ",b[i]/c[i][i]);
    return 0;
}
最后修改:2018 年 12 月 01 日 03 : 46 PM

发表评论

3 条评论

  1. smy

    您的公式有点没写好,那个$a_{i,j}^2$最好写成${a_{i,j}}^2$

    1. M_sea
      @smy

      差不多吧。。。

      1. smy
        @M_sea

        看着不舒服啊qwq