P4035 [JSOI2008]球形空间产生器

P4035 [JSOI2008]球形空间产生器

需要找到一个 $x _ i$ ，使得
$$
\forall i, \sum _ {j = 1} ^ n (p _ {i, j} - x _ j) ^ 2 = r ^ 2
$$
注意到有二次项，不能直接高斯消元。但是可以发现所有的 $x _ j ^ 2$ 项的系数都是相同的，因此可以相邻两个方程相减，同时还可以将 $r ^ 2$ 消掉。

查看代码

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 20;
const double eps = 1e-8;
int n;
double p[N][N], A[N][N];
int Gauss()
{
    int c = 0, r = 0;
    for (; c < n; c++)
    {
        int t = r;
        for (int i = r; i < n; i++)
            if (fabs(A[i][c]) > fabs(A[t][c]))
                t = i;
        if (fabs(A[t][c]) < eps)
            continue;
        for (int i = c; i <= n; i++)
            swap(A[t][i], A[r][i]);
        for (int i = n; i >= c; i--)
            A[r][i] /= A[r][c];
        for (int i = r + 1; i < n; i++)
            if (fabs(A[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    A[i][j] -= A[r][j] * A[i][c];
        r++;
    }
    if (r < n)
    {
        for (int i = r; i < n; i++)
            if (fabs(A[i][n]) > eps)
                return 1;
        return 2;
    }
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; ++j)
            A[i][n] -= A[i][j] * A[j][n];
    return 0;
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < n; j++)
            scanf("%lf", &p[i][j]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            A[i][j] = 2 * (p[i][j] - p[i + 1][j]);
            A[i][n] += p[i][j] * p[i][j] - p[i + 1][j] * p[i + 1][j];
        }
    Gauss();
    for (int i = 0; i < n; i++)
        printf("%.3lf ", A[i][n]);
    return 0;
}