Luogu4035 [JSOI2008]球形空间产生器

发布于 9 天前  11 次阅读


Link

Sol

似乎很久都没有发题解了

看题,现在在 n 维空间中我们要求出这个球的球心。我们可以设球心的坐标为 (r_1, r_2, \dots, r_n) 。根据给出的定义的距离公式,我们可以得到半径和一个球面上的点与球心的关系,即:

R = \sqrt{\sum \left( a_i-r_i\right)^2}

有根号项,同时平方一下,并且把二项式展开

R^2= \sum a_{i}^2 - 2\sum{a_i\times r_i + \sum r_i^2}

那么因为只有关a_i的先均可以视为常数项,将其移至等号右边,这样就得到了一个关于r_in+1一个方程。高斯消元求解即可

Code

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

const int SIZE = 10 + 5;
const int eps = 1e-7;

int n;
double a[SIZE][SIZE];

int main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    scanf("%d", &n); ++ n;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j < n; ++ j) {
            scanf("%lf", &a[i][j]);
            a[i][n + 1] -= a[i][j] * a[i][j]; a[i][j] *= -2.00;
        }
        a[i][n] = 1;
    }
    for (int i = 1, cur; i <= n; ++ i) {
        cur = i;
        for (int j = i + 1; j <= n; ++ j) {
            if (fabs(a[j][i]) > fabs(a[cur][i])) cur = j;
        }
        if (fabs(a[cur][i]) < eps) continue;
        std::swap(a[cur], a[i]);
        for (int j = i + 1; j <= n + 1; ++ j) a[i][j] /= a[i][i];
        a[i][i] = 1.00;
        for (int j = 1; j <= n; ++ j) {
            if (i == j) continue;
            for (int k = i + 1; k <= n + 1; ++ k) a[j][k] -= a[j][i] * a[i][k];
            a[j][i] = 0;
        }
    }
    for (int i = 1; i < n; ++ i) printf("%.3lf ", a[i][n + 1]);
    return 0;
}

学会生存 学会关心