BZOJ1013:[JSOI2008]球形空间产生器题解

解法

这道题其实就是高斯消元裸题。依照题意可以列出形如以下的方程:

\[ \sum_{i = 1}^n (x_a [i] – x_0 [i])^2 = c \]

其中\(c\)表示球的半径。一共有\(n+1\)个这样的方程,可以考虑上下相减消掉常数,这样就构造出了一个\(n\)个方程的方程组。最终方程组:

\[ \begin{cases} 2\sum_{i = 1}^n x_1[i] x_2[i] = \sum_{i = 1}^n (x_1[i])^2 – (x_2[i])^2 \\ 2\sum_{i = 1}^n x_2[i] x_3[i] = \sum_{i = 1}^n (x_2[i])^2 – (x_3[i])^2 \\ 2\sum_{i = 1}^n x_3[i] x_4[i] = \sum_{i = 1}^n (x_3[i])^2 – (x_4[i])^2 \\ \dots \end{cases} \]

扔到高斯消元里就搞定了。

代码

// BZ1013.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 12;
double mat[MAX_N][MAX_N], c[MAX_N], raw[MAX_N][MAX_N];
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j <= n; j++)
            scanf("%lf", &raw[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            mat[i][j] = 2 * (raw[i][j] - raw[i + 1][j]),
            c[i] += raw[i][j] * raw[i][j] - raw[i + 1][j] * raw[i + 1][j];
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            if (fabs(mat[j][i]) > 1e-8)
            {
                for (int k = 1; k <= n; k++)
                    swap(mat[j][k], mat[i][k]);
                swap(c[i], c[j]);
            }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            double rate = mat[j][i] / mat[i][i];
            for (int k = 1; k <= n; k++)
                mat[j][k] -= rate * mat[i][k];
            c[j] -= rate * c[i];
        }
    for (int i = 1; i <= n; i++)
        printf("%.3lf ", c[i] / mat[i][i]);
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注