BZOJ 1013 球形空間產生器：高斯消元法求 n 維球面球心坐標

BZOJ 1013 球形空間產生器：高斯消元法求 n 維球面球心坐標

給定 n+1 個 n 維空間點，求到這 n+1 個點距離相等的點（即超球面球心）。本質是解 n 元線性方程組，高斯消元法完美適用。

數學建模

設球心為 X = (x₁, x₂, ..., xₙ)，第 i 個已知點為 Aᵢ = (aᵢ₁, aᵢ₂, ..., aᵢₙ)。
距離平方相等：|X - Aᵢ|² = |X - Aᵢ₊₁|² (i=1..n)
展開並相減，二次項 |X|² 抵消，得 n 個線性方程：
Σ 2(aᵢ₊₁,ⱼ - aᵢ,ⱼ) xⱼ = Σ (aᵢ₊₁,ⱼ² - aᵢ,ⱼ²)

增廣矩陣構造

double a[12][12]; // a[i][j] 存第 i 個點第 j 維座標 (1-based)
double A[12][12]; // 增廣矩陣 A[i][j] = 2*(a[i+1][j] - a[i][j]), A[i][n+1] = Σ(a[i+1][j]² - a[i][j]²)

第 i 行對應第 i、i+1 個點的方程，共 n 行 n+1 列（最後一列為常數項）。

高斯消元關鍵細節

1. 列主元選擇：每列選 |A[k][i]| 最大的行與當前行交換，提高數值穩定性，避免除零。
2. 消元歸零：對下方各行，倍數 y = A[j][i] / A[i][i]，整行 A[j][k] -= y * A[i][k]。
3. 回代求解：從最後一行向上，xᵢ = (A[i][n+1] - Σ A[i][j]xⱼ) / A[i][i]。

void Gauss() {
    for (int i = 1; i <= n; i++) {
        int mx = i;
        for (int j = i+1; j <= n; j++)
            if (fabs(A[mx][i]) < fabs(A[j][i])) mx = j;
        for (int j = i; j <= n+1; j++) swap(A[mx][j], A[i][j]);
        for (int j = i+1; j <= n; j++)
            if (A[i][i] != 0) {
                double y = A[j][i] / A[i][i];
                for (int k = i; k <= n+1; k++) A[j][k] -= y * A[i][k];
            }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i+1; j <= n; j++) A[i][n+1] -= A[i][j] * A[j][n+1];
        A[i][n+1] /= A[i][i];
    }
}

精度與輸出

題目要求保留 3 位小數。使用 double、列主元、消元歸零標準流程，對 n ≤ 10 足夠穩定。輸出 A[1][n+1] ... A[n][n+1] 即為球心坐標。

複雜度與適用範圍

• 時間 O(n³)，n ≤ 10 瞬間完成。
• 適用於任意維度的球心求解、最小二乘法、多項式擬合等線性方程組問題。

總結

幾何問題代數化 → 線性方程組 → 高斯消元，是計算幾何核心解題路徑。掌握增廣矩陣構造、列主元消元、回代求解標準流程，可解決大數據擬合、機器人運動學逆解等實際工程問題。